【LeetCode Hot 100】#3 无重复字符的最长子串：滑动窗口，两种做法

题目描述

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

示例 1:

"abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

"b"，所以其长度为 1。

示例 3:

"wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

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

解法1

滑动窗口是一种常见的字符串/数组问题的抽象概念。窗口指的是在数组或字符串中由开始索引和结束索引所组成的一系列元素的集合 [left, right]（左右闭区间），而滑动指的是窗口的左右边界可以左右移动。

思路

1. 使用两个指针 left 和 right 维护一个窗口，窗口内的字符都是不重复的
2. right 指针向右扩张窗口，将字符加入 HashSet
3. 如果 right 指向的字符已经在窗口里了，说明出现了重复，此时需要从左侧收缩窗口——移动 left 指针并移除对应字符，直到窗口内不再包含该重复字符
4. 每次移动右指针后，更新最大长度

用 HashSet 来判断字符是否存在于当前窗口中，contains 和 add 操作的平均时间复杂度都是 O(1)。

具体过程

以 "pwwkew" 为例：

• 初始状态：左右指针都在 0，窗口只有 p，max = 1
• 右指针到 1：窗口变为 p, w，无重复，max = 2
• 右指针到 2（遇到 w）：窗口是 [p, w]，右指针的 w 已经存在，从左侧开始删除：移除 p（left=1），窗口还有 w，继续移除 w（left=2），窗口为空，加入当前 w，窗口变为 [w]
• 右指针到 3：窗口变为 [w, k]
• 右指针到 4：窗口变为 [w, k, e]，长度 3，max = 3
• 右指针到 5（遇到 w）：窗口是 [w, k, e]，移除下标 2 的 w（left=3），窗口变为 [k, e]，加入当前的 w，窗口变为 [k, e, w]，长度 3
• 最终结果：3

解答1

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0;  // 左指针
        int n = s.length();
        int max_len = 0;   // 最大长度

        // 右指针开始滑动
        for(int right = 0; right < n; right++){
            char c = s.charAt(right);

            // 如果右指针所指的字符已经在窗口里
            while(set.contains(c)){
                set.remove(s.charAt(left));
                left++;
            }

            set.add(c);
            max_len = Math.max(max_len, right - left + 1);
        }

        return max_len;
    }
}

复杂度分析

• 时间复杂度： O(n)，每个字符最多被 left 和 right 各访问一次
• 空间复杂度： O(k)，k 为字符集大小，HashSet 中最多存储 k 个字符

存在的问题

虽然 HashSet 解法逻辑清晰、容易理解，但 HashSet 存储的是 Character 对象，每次 add 和 contains 操作都会涉及装箱/拆箱和哈希计算，常数时间开销较大。此外，遇到重复字符时，while 循环让 left 一个一个往右移，每个元素可能被重复访问，最坏情况下时间复杂度达到 O(2n)。

解法2（解法1的优化）

优化一：用数组代替 HashSet

由于题目中字符串由英文字母、数字、符号和空格组成，属于 ASCII 字符集，范围是 0~128。我们可以用一个长度为 128 的整型数组 int[] 来代替 HashSet，数组的索引就是字符的 ASCII 码，数组的值记录该字符在字符串中上一次出现的下标。这样避免了装箱/拆箱和哈希计算的开销，速度更快。

优化二：跳跃式更新左指针

解法1中，遇到重复字符时是用 while 循环让 left 一步一步往右移。但我们可以更进一步：由于我们记录了每个字符上一次出现的下标，遇到重复字符时，可以直接把 left 跳到该字符上次出现位置的下一个位置，而不需要一个一个移动。

具体过程

以 "pwwkew" 为例：

• 遍历到下标 2 的 w 时，发现 w 上次出现的位置是 1，且 1 >= left（0），说明 w 在当前窗口内
• 直接把 left 跳到 last['w'] + 1 = 2
• 窗口瞬间变为 [w]，从 O(window_size) 的逐步收缩变成了 O(1) 的跳跃

这里的 left = Math.max(left, last[c] + 1) 是一个关键细节：取最大值是为了确保 left 不会回退。如果重复字符出现在当前窗口之前的位置（即 last[c] < left），说明它已经不在窗口内了，此时不应该移动 left。

解答2

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 记录字符上一次出现的位置，初始化为 -1
        int[] last = new int[128];
        Arrays.fill(last, -1);
  
        int left = 0;
        int maxLen = 0;
        int n = s.length();
  
        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
  
            // 如果该字符出现过，且在窗口内（last[c] >= left），直接跳跃 left
            left = Math.max(left, last[c] + 1);
  
            // 更新该字符最后出现的位置
            last[c] = right;
  
            // 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
  
        return maxLen;
    }
}

复杂度分析

• 时间复杂度： O(n)，right 指针只遍历一次字符串，left 指针直接跳跃而非逐步移动，每个字符最多被访问一次
• 空间复杂度： O(1)，数组大小固定为 128