BzCode

无重复字符的最长子串

给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1：

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10⁴
s 由英文字母、数字、符号和空格组成

解题思路：

Q: 暴力枚举所有子串并检查重复，时间复杂度是多少？ O(n²)，需要优化。

Q: 用窗口 [left, right] 圈出一段无重复子串，right 右移时新字符与窗口内某字符重复了，left 该怎么动？跳到「那个重复字符上次出现位置 + 1」，一步到位，绝不回退。

Q: 怎么在 O(1) 时间查到某字符上次出现的下标？哈希表 字符 → 上次下标。

Q: 串 "abba" 走到最后的 a 时，a 上次在下标 0，但此时 left 已在 2，直接令 left = 上次位置+1 会让 left 退回 1，错把已踢掉的 b 包回窗口。如何避免 left 回退？加判断：只有当重复字符在当前窗口内才移动 left。

Q: 怎么判断「重复字符在不在当前窗口 [left, right] 内」？是 pos > left 还是 pos >= left？ pos >= left。等于时重复字符正好在窗口最左端，仍属窗口内，必须移动。

Q: 更新「最长长度」放在 if 内还是 if 外？ if 外，每轮 right 前进后都更新。否则像 "abc" 这种全程无重复的串，if 一次都不进，会漏掉答案。

整体思路：

滑动窗口 + 哈希记录每个字符最近出现的下标。right 逐位右移，若当前字符上次出现位置 pos >= left（即落在窗口内），则把 left 跳到 pos + 1；每轮无条件更新该字符位置，并用 right - left + 1 刷新最大长度。每个字符进出窗口各一次，O(n)。

C++（unordered_map 版）

cpp

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int  left=0,right=0;
        int n=s.size();
        int res=0;
        unordered_map<char,int> posMap;
        for(right=0;right<n;right++){
            if(posMap.count(s[right])&&posMap[s[right]]>=left){
                left=posMap[s[right]]+1;
            }
            posMap[s[right]]=right;
            res=max(res,right-left+1);
        }
        return res;
    }
};

Java

java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> posMap = new HashMap<>();
        int left = 0, res = 0, n = s.length();
        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            if (posMap.containsKey(c) && posMap.get(c) >= left) {
                left = posMap.get(c) + 1;
            }
            posMap.put(c, right);
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

Python

python

from typing import Dict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        pos_map: Dict[str, int] = {}
        left: int = 0
        res: int = 0
        n: int = len(s)
        for right in range(n):
            c: str = s[right]
            if c in pos_map and pos_map[c] >= left:
                left = pos_map[c] + 1
            pos_map[c] = right
            res = max(res, right - left + 1)
        return res

Go（map 版，用「逗号 ok」判断键存在）

func lengthOfLongestSubstring(s string) int {
    posMap := make(map[byte]int)
    left, res := 0, 0
    for right := 0; right < len(s); right++ {
        c := s[right]
        if pos, ok := posMap[c]; ok && pos >= left {
            left = pos + 1
        }
        posMap[c] = right
        res = max(res, right-left+1)
    }
    return res
}

时间复杂度 O(n)，空间复杂度 O(min(n, 字符集大小))。

无重复字符的最长子串 ​

无重复字符的最长子串