3. 无重复字符的最长子串

难度：🟡 Medium | 标签：滑动窗口、哈希 | 状态：⬜ LeetCode 链接

思路

滑动窗口 + 哈希。右指针扫字符，遇到窗口内已存在的字符，左指针收缩到该字符旧位置 + 1。

用 last[c] 存字符最近一次出现的下标，O(1) 跳转。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int last[128];
        fill(begin(last), end(last), -1);
        int l = 0, best = 0;
        for (int r = 0; r < (int)s.size(); ++r) {
            if (last[(int)s[r]] >= l) l = last[(int)s[r]] + 1;
            last[(int)s[r]] = r;
            best = max(best, r - l + 1);
        }
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(Σ)（字符集 128）

易错 / 回顾

• last[c] >= l 判断很关键：旧位置在窗口外就别动 l
• 不要用 set 然后 while 弹左，那是 O(n²) 最坏
• ASCII / Unicode：题目限定 ASCII 时直接开 128 数组，性能优于 map