无重复字符的最长子串

这道题要求找出字符串中不包含重复字符的最长子串的长度。注意是子串（连续），不是子序列，返回的是长度，不是子串本身。

最直观的想法

第一次看到这题，我想到的是：枚举所有可能的子串，判断每个是否无重复，取最长的。

两层循环，外层遍历起点，内层遍历终点，对每个子串检查是否有重复字符。这是最"暴力"的方法：

var lengthOfLongestSubstring = function(s) {
    let maxLen = 0
    
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            if (isUnique(s, i, j)) {
                maxLen = Math.max(maxLen, j - i + 1)
            }
        }
    }
    
    return maxLen
}

function isUnique(s, left, right) {
    const set = new Set()
    for (let i = left; i <= right; i++) {
        if (set.has(s[i])) return false
        set.add(s[i])
    }
    return true
}

时间复杂度 O(n³)，对于长字符串会超时。

问题在哪？

这个方法做了很多重复工作。比如我们判断 s[0...4] = "abcab" 有重复，然后判断 s[0...5] = "abcabc" 时，又重新检查了 s[0...4]，这是重复的。

而且，如果我们知道 s[i...j] 是无重复的，当 s[j+1] 加入时：

• 如果 s[j+1] 不在 s[i...j] 中，那么 s[i...j+1] 也是无重复的
• 如果 s[j+1] 在 s[i...j] 中（比如在位置 k），那么 s[i...j+1] 有重复，但 s[k+1...j+1] 可能是无重复的

滑动窗口

这就是滑动窗口的思路。我们维护一个窗口 [left, right]，窗口内的字符都是无重复的。右边界 right 不断向右扩展，如果遇到重复字符，左边界 left 向右收缩，直到窗口内无重复。

用 Set 记录窗口中的字符，快速判断是否有重复：

var lengthOfLongestSubstring = function(s) {
    const set = new Set()
    let left = 0
    let maxLen = 0
    
    for (let right = 0; right < s.length; right++) {
        // 如果当前字符在窗口中，收缩左边界
        while (set.has(s[right])) {
            set.delete(s[left])
            left++
        }
        
        // 加入当前字符
        set.add(s[right])
        
        // 更新最大长度
        maxLen = Math.max(maxLen, right - left + 1)
    }
    
    return maxLen
}

时间复杂度 O(n)，每个字符最多被访问两次（一次被 right 访问，一次被 left 访问）。

优化：直接跳跃

上面的方法中，遇到重复时 left 是一步一步移动的。我们可以优化：用 Map 记录字符的最后出现位置，遇到重复时直接跳跃到重复字符的下一个位置。

var lengthOfLongestSubstring = function(s) {
    const map = new Map()
    let left = 0
    let maxLen = 0
    
    for (let right = 0; right < s.length; right++) {
        if (map.has(s[right])) {
            // 直接跳跃到重复字符的下一个位置
            // 注意：left 可能已经超过了这个位置，所以用 Math.max
            left = Math.max(left, map.get(s[right]) + 1)
        }
        
        map.set(s[right], right)
        maxLen = Math.max(maxLen, right - left + 1)
    }
    
    return maxLen
}

为什么用 Math.max？因为 left 可能已经超过了 map.get(s[right]) + 1。比如 s = "abba"：

• right=2 时，'b' 重复，left 跳到 2
• right=3 时，'a' 重复，但 left 已经是 2 了，不能往回跳到 1

这道题在考什么？

这道题的核心是滑动窗口。滑动窗口是处理"连续子串"、"连续子数组"问题的经典方法：

• 维护一个始终满足条件的窗口
• 右边界扩展，遇到不满足条件时，左边界收缩

哈希表（Set/Map）用来快速判断"某个字符是否在窗口中"，这是滑动窗口的常见搭配。

下次遇到类似题目，看到"连续子串"、"子数组"、"无重复"、"最长"这些关键词，就应该想到滑动窗口。比如最小覆盖子串、找到字符串中所有字母异位词这些题，都是滑动窗口的变种。

记忆要点：

• 连续子串 → 滑动窗口
• 无重复 → Set/Map
• 右扩展，左收缩 → 滑动窗口的经典模式