网站建设实训步骤,免费网站建设好不好,短视频制作培训班,app制作培训题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer#xff08;专项突击版#xff09;系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
给定一个字符串 s #xff0c;请你找出其中不含有重复字符的最长… 题目难度: 中等 原题链接 今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~ 题目描述
给定一个字符串 s 请你找出其中不含有重复字符的最长连续子字符串的长度。
示例 1:
输入: s “abcabcbb”输出: 3解释: 因为无重复字符的最长子字符串是 “abc”所以其长度为 3。
示例 2:
输入: s “bbbbb”输出: 1解释: 因为无重复字符的最长子字符串是 “b”所以其长度为 1。
示例 3:
输入: s “pwwkew”输出: 3解释: 因为无重复字符的最长子串是 “wke”所以其长度为 3。 - 请注意你的答案必须是 子串 的长度“pwke” 是一个子序列不是子串。
示例 4:
输入: s “”输出: 0
提示
0 s.length 5 * 10^4s 由英文字母、数字、符号和空格组成
题目思考
如何通过一次遍历得出结果?如果统计当前子字符串的字符种类?
解决方案
思路
分析题目, 一个最简单的思路就是暴力法: 固定子字符串起点, 然后往后扩展, 因为不能含有重复, 所以可以使用集合统计当前子字符串的字符种类, 直到发现重复字符或者到终点停止, 取最长的子字符串作为结果. 但这样需要两重遍历, 时间复杂度达到 O(N*C) (C 是字符的种类数目, 因为找到重复就会停下来, 所以不是 N^2), 不是很优基于暴力法进行分析, 假设当前子字符串起点是 start, 发现重复字符的位置是 end, 然后对应的该字符上个下标是 dup, 显然start dup end此时暴力法的做法是将 start1 重新开始遍历子字符串, 但这样做完全没有必要, 因为以[start1, dup]中的任一下标作为起点的字符串肯定都会在 end 处停下来, 因为找到了重复的(end 和 dup), 而且这些子字符串长度必然小于以 start 为起点的所以更优化的做法是将起点向后遍历到 dup1, 从字符集合中移除遍历过程中的字符, 然后将 dup1 作为新的起点, 终点继续从 end 处开始遍历, 直到再次遇到重复字符, 重复上述步骤即可这样起点和终点都只需要遍历一遍, 相比暴力法有所优化以上就是典型的滑动窗口的思想, 通常做法就是维护双指针代表窗口起点和终点, 然后根据当前窗口是否满足要求来进行不同的处理下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
时间复杂度 O(N): 起点和终点都只需要遍历一遍空间复杂度 O(1): 只使用了几个变量
代码
class Solution:def lengthOfLongestSubstring(self, s: str) - int:# 滑动窗口当前字符集合, 时刻更新resstart 0res 0v set()for end in range(len(s)):c s[end]if c in v:# 发现重复了, start向后遍历找dup下标(即上一个c的下标)while start end and s[start] ! c:v.remove(s[start])start 1# 此时dup start, 需要将dup1作为新的起点start 1else:# 没有重复, 将当前字符加入字符集合中v.add(c)# 最大子字符串长度就是最大的字符集合的长度, 当然此处也可以用end-start1代替res max(res, len(v))return res大家可以在下面这些地方找到我~ 我的 GitHub 我的 Leetcode 我的 CSDN 我的知乎专栏 我的头条号 我的牛客网博客 我的公众号: 算法精选, 欢迎大家扫码关注~
