分析

根据题目要求，要求无重复的连续最长子串。

示例 1:

输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 “bca” 和 “cab” 也是正确答案。

示例 2:

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

示例 3:

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

---

题解

滑动窗口

我们可以通过维护一个滑动窗口来统计子串的大小，然后不断更新最大的子串长度。

哈希记录字符最新下标（标准滑动窗口）

核心：

• map存：字符 -> 该字符上一次出现的下标
• 如果s[r]在map中，并且上一次下标>= 1，说明在窗口内重复，移动左边界：l = max(l, hashTable[s[r]] + 1)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hashTable;
        int res = 0;
        int l = 0;
        for(int r = 0; r < s.size(); ++r) {
            // 当前字符出现过，并且落在窗口[l, r‑1]里面
            if(hashTable.find(s[r]) != hashTable.end() && hashTable[s[r]] >= l) {
                l = hashTable[s[r]] + 1;
            }
            // 更新当前字符最新的位置
            hashTable[s[r]] = r;
            res = max(res, r - l + 1);
        }
        return res;
    }
};

l = hashTable[s[r]] + 1;

• hashTable[s[r]]：字符s[r]上一次出现的下标（0-based）
• +1：左边界跳到重复字符上一次位置的下一个位置

补充小优化 字符只有ASCII，可以不用unordered_map，直接用数组int last[128]，速度更快：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int last[128];
        memset(last, -1, sizeof(last));
        int l = 0, res = 0;
        for(int r = 0; r < s.size(); r++){
            char c = s[r];
            if(last[c] >= l){
                l = last[c] + 1;
            }
            last[c] = r;
            res = max(res, r-l+1);
        }
        return res;
    }
};

时间复杂度$\boldsymbol{O(n)}$

r 从 0→n‑1；l 整体只会从 0→n‑1，总共移动不超过 n 次。虽然没有显式while，本质双指针，每个指针最多走 n 步。

空间复杂度

• unordered_map：$O(min(m,n))$，m 是字符集大小；最多存字符串里不同字符
• int lastPos [128] 数组：$O(1)$，固定 128，常数空间

核心：保存下标，直接跳跃左边界，不需要一格一格收缩窗口。

---

计数版滑动窗口（窗口内字符计数）

map记录窗口内每个字符出现次数，当右指针遇到字符计数等于1（窗口已经存在），不断收缩左边界直到重复消失。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> cnt;
        int l = 0, res = 0;
        for(int r = 0; r < s.size(); r++) {
            char c = s[r];
            cnt[c]++;
            while(cnt[c] > 1) {
                cnt[s[l]]--;
                l++;
            }
            res = max(res, r - l + 1);
        }
        return res;
    }
};

时间复杂度$\boldsymbol{O(n)}$

误区：看到 for 套 while 以为$O(n^2)$，不是。

l 只会增加，整个算法全过程，l++一共最多执行 n 次。

for 循环 n 次，while 里面总执行次数≤n，总操作数 ≤ 2n，$O(n)$。

举极端例子s = "aaaaa"

• r 每往前走一步，while 就 l++ 一次；全部加起来 l 一共从 0 走到 n‑1。总操作 O (n)。

空间复杂度

同样：

• unordered_map 计数：$O(min(m,n))$
• 数组计数：$(O(1)$

---

两者对比表

维度	下标记录版（跳跃 l）	计数 while 版（逐格收缩）
核心信息	存字符最后下标	存窗口内字符出现次数
左边界移动	直接跳跃 l = old_pos+1	while 循环，l++一格一格挪
循环结构	单层 for，无内层循环	for 嵌套 while
时间复杂度	O(n)	O(n)
空间 (map)	O(min(m,n))	O(min(m,n))
空间 (ASCII 数组)	O(1)	O(1)
适合场景	知道字符上次位置，快速跳转	通用滑动窗口模板（很多题复用这套 while 模板）

⚠重要：嵌套 while 不等于平方复杂度，要看指针总移动步数！双指针滑动窗口绝大多数都是 O (n)。

3. 无重复字符的最长子串 - 力扣（LeetCode）