【LeetCode】3. 无重复字符的最长子串

题目链接

Python3

方法：滑动窗口 $⟮O(N),O(1)⟯$

写法一

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """滑动窗口"""
        ### 处理特殊情况
        if len(s)== 0: return 0

        ## 处理一般情况
        res = 0
        left, right = 0, 0
        while right < len(s):
            if s[right] not in s[left:right]:  # 窗口 右侧 扩展
                res = max(res, right - left + 1)
                right += 1                
            else: ## 因为要是 重复的元素  在窗口中间，left 要一直后移，这时窗口是变小的，在这里更新 maxlen 意义不大，也不会更新
                left += 1

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

写法二

写法二： 在 窗口中 定位重复字符位置，直接移动 左侧下标

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """滑动窗口"""
        ### 处理特殊情况
        if len(s)== 0: return 0

        ## 处理一般情况
        res = 0
        left, right = 0, 0
        while right < len(s):
            if s[right] not in s[left:right]:  # 窗口 右侧 扩展
                res = max(res, right - left + 1)
                right += 1                
            else: 
                left += s[left:right].index(s[right]) + 1   # 注意这里是要加上

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

写法三：哈希表 记录 字符 在窗口中的最新位置

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:  return 0

        start = -1  # 窗口 左边下标
        dic = {} # 记录 窗口中  每个字符出现的位置
        res = 0

        for i in range(len(s)):
            if s[i] in dic and dic[s[i]] > start: # 窗口 中重复
                start = dic[s[i]]  # 窗口 左侧下标 更新
                dic[s[i]] = i   # 更新该字符 位置
            else: # 未出现重复
                dic[s[i]] = i  # 添加新字符
                res = max(res, i - start) # 更新长度

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C++

方法：滑动窗口 $⟮O(N),O(1)⟯$

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> dic;
        int left = -1, res = 0;
        for (int right = 0; right < s.size(); ++right){
            auto it = dic.find(s[right]);
            if (it !=  dic.end()){
                left = max(left, it->second);
            }
            dic[s[right]] = right;
            res = max(res, right - left);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

错误版本：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0){
            return 0;
        }

        int left = 0, right = 0, res = 0;
       // unordered_map dic; // 字符：窗口中的位置
        while (right < s.size()){
            if (s.substr(left, right-left).find(s[right])){
                res = max(res, right - left + 1);
                ++right;
            }
            else{
                ++left;
            }

        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

substr(起始下标， 长度)

文档
从字符串起始处的指定位置复制最多某个数目的字符的子字符串。