LeetCode Hot 100 | 8. 无重复的最长子串

核心思维

这道题是 滑动窗口 (Sliding Window) 的经典应用。核心在于利用窗口的"单调性"来优化暴力解法。

• 推导逻辑（为什么不回退）： 假设以下标 i 开始的子串，最长能延伸到下标 rk（即 s[i...rk] 无重复）。当我们寻找以 i+1 开始的子串时，由于 s[i+1...rk] 是 s[i...rk] 的子集，它必然也没有重复字符。因此，右边界 rk 不需要回退，只需要从当前位置继续尝试向右扩展 (rk+1, rk+2...) 即可。

  结论： 左指针向右移动一格，右指针从未移动过的地方继续向右，绝不回头。

• 数据结构选择： 使用 哈希集合 (unordered_set) 作为窗口内容的容器。

  • 作用： O(1) 时间复杂度判断字符是否存在，实现"查重"。
  • 机制： 窗口右移进元素 (insert)，窗口左移出元素 (erase)。

算法流程

使用双指针维护一个动态窗口：

• 左指针 i：代表当前子串的起始位置，通过 for 循环逐步向右移动。
• 右指针 currentMaxIndex：代表当前子串的结束位置，初始为 -1。

步骤拆解：

1. 初始化： 定义最大长度 result = 0，右指针 currentMaxIndex = -1，哈希集合 uSet。
2. 移动左边界： 遍历 i 从 0 到 n-1。
   • 如果 i > 0（即不是第一次进入循环），说明左边界向右缩进了一格，需要在集合中移除上一个左边界的字符 s[i-1]。
3. 扩展右边界： 在循环内部使用 while：
   • 检查条件： 下一个位置 currentMaxIndex + 1 是否越界？且该字符是否不在集合中？
   • 执行扩展： 如果满足，将该字符加入集合，并将 currentMaxIndex 右移。
4. 更新结果： 每一轮扩展结束后，当前窗口长度为 currentMaxIndex - i + 1，更新 result。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，记录当前窗口 [i, currentMaxIndex] 内的所有字符
        unordered_set<char> uSet;
        int result = 0;
        
        // currentMaxIndex 相当于右指针 rk，初始化为 -1 表示窗口还没开始
        // 它的含义是：当前窗口内【最后一个有效字符】的下标
        int currentMaxIndex = -1; 

        // i 是左指针，逐步向右收缩
        for (int i = 0; i < s.size(); i++) {
            // 1. 左边界收缩：
            // 只要 i > 0，说明左指针移动了，需要把移出窗口的字符(即前一个字符)从集合中删掉
            if(i > 0){
                uSet.erase(s[i-1]);
            }

            // 2. 右边界扩展：
            // 核心思考：为什么要检查 currentMaxIndex + 1？
            // 答：这是一种"前瞻 (Lookahead)" 机制。
            // 我们在移动指针之前，先检查"下一步"是否合法（不越界且无重复）。
            // 只有合法时，才真正移动指针并加入集合。这样保证了 uSet 里永远没有重复元素。
            while (currentMaxIndex + 1 < s.size() && uSet.find(s[currentMaxIndex + 1]) == uSet.end()) {
                uSet.insert(s[currentMaxIndex + 1]);
                currentMaxIndex++;
            }

            // 3. 更新结果：
            // 当前合法窗口范围是 [i, currentMaxIndex]，长度为 currentMaxIndex - i + 1
            result = max(result, currentMaxIndex - i + 1);
        }
        
        return result;
    }
};

深度思考

为什么要检查 currentMaxIndex + 1 (下一个元素)，而不是移动后再检查？

核心在于 "保持循环不变量 (Loop Invariant)"。

• 策略 A (移动后检查)： 先把元素加进去，发现重复了，再通过左指针缩圈直到重复消除。这是另一种写法，但逻辑较复杂。
• 策略 B (检查后移动)：
  • while 循环保证了只要能进循环，加进来的元素一定是安全的。
  • 这意味着 uSet 在任何时刻都严格只包含无重复字符。
  • 结束条件可控： 当 while 停下来时，明确知道是因为遇到了重复字符（或者到了末尾）。此时直接计算长度即可，逻辑非常清晰。

复杂度分析

• 时间复杂度：O(N) 虽然代码里有两层循环（for 嵌套 while），但请注意：
  • 左指针 i 从 0 走到 N-1。
  • 右指针 currentMaxIndex 也只能从 0 走到 N-1，从不回退。
  • 每个字符最多被 insert 一次，被 erase 一次。总操作次数是线性的。
• 空间复杂度：O(|Sigma|) 其中 |Sigma| 是字符集的大小。对于 ASCII 码，空间最多为 128 或 256，可以视为 O(1)。