LeetCode 3. 无重复字符的最长子串：用不变量把 O(n²) 压到 O(n)

「求最长无重复子串」大概是面试出场率最高的字符串题之一：它短到十分钟可以写完，又深到能连续追问五六层——为什么内层循环不影响复杂度、哈希表该记下标还是记计数、abba 为什么会让一种流行写法悄悄出错。这道题真正的价值不在答案本身，而在它第一次把「滑动窗口 + 不变量」这套思维完整地摆在面前：先承认暴力在重复劳动，再让两个指针各自单调前进，用一条恒成立的性质换取线性复杂度。本文所有代码都已在本地用题面用例、边界用例与 500 轮随机差分（以暴力为基准）验证通过，n 取 10^5 时毫秒级出结果。

题目回顾

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

约束条件：0 <= s.length <= 10^5，s 由英文字母、数字、符号和空格组成。这两条都值得多看一眼。第一，n 可以为 0，空串是合法输入，答案为 0——用「先取 s[0] 再进循环」起手的写法在这里会直接抛异常。第二，n 最大到 10^5，任何 O(n²) 以上的做法都要掂量一下：10^5 的平方是 10^10，量级上就已经出局，题目在暗示你找线性做法。第三，「字母、数字、符号和空格」意味着字符集是 ASCII 可打印字符，规模不超过百级——这给空间复杂度定了上界，后文复杂度分析会用到。

示例有三个，信息量各有侧重：

s = "abcabcbb" 输出 3，最长无重复子串是 "abc"；注意 "bca"、"cab" 也都是合法答案——题目只要长度，不要求还原具体子串。
s = "bbbbb" 输出 1，全相同字符把窗口压到最短。
s = "pwwkew" 输出 3，最长是 "wke"；题面特意强调 "pwke" 是子序列而不是子串——子串必须连续，跳过中间的 w 就不合法了。这是审题层面的第一大陷阱。

暴力解法与它的瓶颈

最直接的想法：全枚举

把所有子串枚举一遍，逐个检查是否含重复字符，取无重复者的最大长度：

// 暴力：枚举每个子串，逐个检查是否无重复 —— O(n^3)
function lengthOfLongestSubstringBrute(s) {
  const n = s.length;
  let ans = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      const seen = new Set();
      let ok = true;
      for (let k = i; k <= j; k++) {
        if (seen.has(s[k])) { ok = false; break; }
        seen.add(s[k]);
      }
      if (ok) ans = Math.max(ans, j - i + 1);
    }
  }
  return ans;
}

外层两重循环枚举起点 i 与终点 j，子串共有 n(n+1)/2 个，即 O(n²) 个；每个子串用哈希集合查重需要 O(n)。总代价 O(n²·n)，也就是 O(n³)。代入 n = 10^5，操作数约 10^15——就算每秒做十亿次操作也要跑上百小时。这个解法在 LeetCode 上连中等规模的用例都过不去，但它是最好的起点：所有优化都始于看清暴力到底在重复什么。

重复劳动在哪

盯住相邻两次内层检查：刚查完 s[i..j] 无重复，转脸查 s[i..j+1] 时又从 s[i] 数起——可前一次的结论明明还在手里。同理，起点换成 i+1 后，s[i+1..j] 的查重信息也早就隐含在上一步里。暴力把 O(n²) 个子串当成彼此无关的问题各算一遍，而事实上相邻子串之间只差一个字符。把「每步只多一个字符」利用起来，就是滑动窗口的全部动机。

顺着这个思路还能得到一个中间版本：固定起点 i，让 j 一路右移直到撞上第一个重复字符才停下，途中带着集合增量查重。最坏情况（比如全不同）仍是 O(n²)，但已经能通过本题——因为字符集不超过百级，j 至多右移百余步就会撞车。这个「够用但不漂亮」的版本是面试官追问「还能再快吗」时你自己应该主动越过的一站。

滑动窗口：一个不变量压到 O(n)

把「查重」变成「维护」

既然相邻子串只差一个字符，就让右指针 right 每次只前进一格，把新字符 s[right] 增量放进一个集合；一旦发现它已经在窗口里，就把左端字符逐个移出集合、left 逐格右移，直到冲突解除。全程维护一条不变量：集合里的字符，恰好是当前窗口 s[left..right] 里的字符，且互不重复。窗口合法时随手用 right - left + 1 更新答案。

// 滑动窗口 + 集合：右端扩张，遇重复逐格收缩左端 —— O(n)
function lengthOfLongestSubstringSet(s) {
  const window = new Set();
  let left = 0, ans = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    while (window.has(c)) {
      window.delete(s[left]);
      left++;
    }
    window.add(c);
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
}

为什么不漏解

正确性论证只有两句话。第一，对每个 right，代码停下来时 left 恰好是「以 right 结尾的无重复子串」的最小起点——while 循环只在窗口非法时才收缩，一旦合法立即停止，所以从不多缩；于是 right - left + 1 正是「以 right 结尾」这一类答案里最长的那个。第二，任何一个最优子串总有某个右端点 right*，它在「以 right* 结尾」这一类里不会漏。两类合起来，全局最优必然被 ans 捕获。

为什么是 O(n)

直觉上两层循环嵌套该是 O(n²)，但这里不是：left 与 right 各自只增不减，right 从 0 走到 n-1 共 n 步，left 每次收缩累积也不会超过 n 步——内层 while 的总执行次数摊到整个运行过程里是 n 次。两个指针合计至多 2n 次单步移动，总复杂度 O(n)，这就是双指针的摊还分析。换个角度看也一样：窗口内无重复，而字符集不超过百级，窗口长度被 Σ 封了顶，每个字符至多进窗一次、出窗一次。空间上，集合最多装 min(n, Σ) 个字符，即 O(min(n, Σ))。

至此四种解法可以放在一张表里了：

解法	时间	空间	核心思想
全枚举逐一检查	`O(n³)`	`O(min(n, Σ))`	枚举 `O(n²)` 个子串，各查重 `O(n)`
起点延伸法	`O(n·Σ)`	`O(min(n, Σ))`	固定起点右移，撞到重复即停
窗口 + 集合	`O(n)`	`O(min(n, Σ))`	不变量：窗口内字符互不重复
窗口 + 记下标	`O(n)`	`O(min(n, Σ))`	`left` 直接跳到重复字符的下一格
窗口 + 记计数	`O(n)`	`O(min(n, Σ))`	违反不变量就收缩，直到恢复

两种窗口收缩写法：记下标与记计数

集合版要收缩多少格，取决于重复字符离左端多远，最坏一趟要把窗口排空。哈希表能把这件事做得更聪明——把「重复字符在哪」直接记下来，就衍生出两种经典写法。

写法一：哈希表记下标，left 跳跃

让哈希表记录每个字符最近一次出现的下标。当新字符 c 与窗口内某字符冲突时，冲突对象只可能是 c 自己，而它的上一个位置一查便知，于是 left 不必逐格挪，直接跳到「上一位置加一」：

// 滑动窗口 + 哈希表记下标：左端直接跳到重复字符的下一格 —— O(n)
function lengthOfLongestSubstringIndex(s) {
  const lastIndex = new Map(); // 字符 -> 最近一次出现的下标
  let left = 0, ans = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (lastIndex.has(c) && lastIndex.get(c) >= left) {
      left = lastIndex.get(c) + 1;
    }
    lastIndex.set(c, right);
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
}

两个细节撑起正确性。其一，为什么只处理新字符 c 的冲突就够了？因为 left 单调右移，此前每次冲突都把对应旧下标甩到了窗口外，lastIndex 里可能残留「出窗」的陈旧记录——这正是条件里 lastIndex.get(c) >= left 的用途：只有下标还在窗口内（不小于 left）才算真冲突，否则保持 left 不动。其二，left = lastIndex.get(c) + 1 是一次 O(1) 赋值，跳跃之后窗口 [left, right] 依然无重复，不变量在跳变中保持成立。

写法二：哈希表记计数，逐格收缩

第二种写法让哈希表记录每个字符在窗口内的出现次数。新字符入窗后计数加一，一旦它超过 1，说明不变量被破坏，就把左端字符计数减一、left 右移，反复收缩直到 c 的计数回到 1：

// 滑动窗口 + 哈希表记计数：靠收缩恢复「窗口无重复」的不变量 —— O(n)
function lengthOfLongestSubstringCount(s) {
  const count = new Map(); // 字符 -> 窗口内出现次数
  let left = 0, ans = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    count.set(c, (count.get(c) || 0) + 1);
    while (count.get(c) > 1) {
      const d = s[left];
      count.set(d, count.get(d) - 1);
      if (count.get(d) === 0) count.delete(d);
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
}

减到 0 就把键删掉是个值得保留的小习惯：这样 count.size 始终等于窗口内的字符种类数，下一节的泛化直接依赖这个性质。两种写法的复杂度同为 O(n)——记下标版每步 O(1)、常数更小；记计数版虽然逐格收缩，但每个字符依旧至多进出窗口各一次。

怎么选

只解本题、追求常数：记下标版。跳跃一步到位，逻辑最短，也是各语言题解里流传最广的版本。
面试与工程：记计数版。它的骨架是「扩张，违反不变量就收缩到恢复」，收缩条件可以整体替换，能原样迁移到一大类窗口题（下一节泛化就是现成例子）；记下标版则依赖「冲突对象必是新字符自身」这一特殊结构，换了问题就得推倒重来。
Python 读者可对照记下标版的直译实现：

# 滑动窗口 + 哈希表记下标（Python 对照版）
def lengthOfLongestSubstring(s: str) -> int:
    last_index = {}   # 字符 -> 最近一次出现的下标
    left = 0
    ans = 0
    for right, c in enumerate(s):
        if c in last_index and last_index[c] >= left:
            left = last_index[c] + 1
        last_index[c] = right
        ans = max(ans, right - left + 1)
    return ans

边界用例与常见错误

边界用例

写完先过这张清单，每个格子都对应一类实现漏洞：

输入	期望输出	考察点
`""`	`0`	约束允许空串，别先取 `s[0]`
`"a"`	`1`	单字符，循环体走一遍
`"bbbbb"`	`1`	全相同，收缩逻辑反复触发
`"abcdef"`	`6`	全不同，`right` 走到底不收缩
`" "`	`1`	空格也是普通字符，照常入窗
`"!?"`	`2`	符号与字母同权
`"abba"`	`2`	陈旧下标陷阱（见错误二）
`"tmmzuxt"`	`5`	重复字符出窗后又回来

其中 " " 与 "!?" 专门对应约束里「符号和空格」：空格开头、纯符号的串都是合法输入，把它们当特殊值跳过反而会错。"tmmzuxt" 值得手动模拟一遍：处理到末尾的 t 时，t 的上一次出现早已被甩出窗口，靠的正是 >= left 这道判断挡住了误跳。

错误一：收缩条件写成「大于」

把真冲突的判断从 lastIndex.get(c) >= left 手滑写成 >——漏掉了「恰好等于 left」的情形。在 "aa" 上就会翻车：处理第二个 a 时，旧下标是 0，left 也是 0，0 > 0 不成立，不收缩，窗口被当成 "aa"，输出 2 而正确答案是 1。相等意味着重复字符就站在窗口左端点上，必须收缩，边界上的等号不能丢。

错误二：漏掉「下标可能已出窗」

反过来，只写 if (lastIndex.has(c)) 就跳，left 会被陈旧下标拽着倒退。经典反例是 "abba"：处理末尾 a 时，它记录的下标是 0，而 left 已到 2，0 开头的记录早该作废；无守卫的版本会把 left 跳回 1，窗口 "bba" 含重复，输出 3，正确答案是 2。这也是面试官最爱挖的坑——追问一句「abba 你的代码输出多少」，写法是否有守卫当场现形。

错误三：收缩不彻底或忘了删字符

两个同源的毛病。一是把收缩循环写成 if：每步至多收缩一格，可能还没恢复不变量就继续扩张。在 "abcbd" 上实测：if 版输出 4（把含重复的 "bcbd" 当成了合法窗口），正确答案是 3——收缩循环必须用 while，恢复不变量这件事要做到底。二是集合版收缩时只 left++、忘了 window.delete(s[left])：集合里留下「幽灵字符」，要么窗口虚长，要么 while (window.has(c)) 条件永远为真直接死循环。收缩移动左端点时，移出的字符必须同步移出集合，这条纪律没有例外。

延伸：至多 K 个不同字符与相关题

泛化：窗口模板的真正威力

把问题换成 LeetCode 340：求至多包含 K 个不同字符的最长子串。刚才记计数版的价值立刻显现——不变量从「每种字符至多一个」换成「种类数至多 K」，收缩条件从「c 的计数超过 1」换成「种类数超过 k」，其余一行不改。靠 count.size 直接读出种类数（这正是上一节「减到 0 就删键」的回报）：

// 泛化：至多包含 K 个不同字符的最长子串（LeetCode 340）—— O(n)
function lengthOfLongestSubstringKDistinct(s, k) {
  if (k === 0) return 0;
  const count = new Map(); // 字符 -> 窗口内出现次数
  let left = 0, ans = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    count.set(c, (count.get(c) || 0) + 1);
    while (count.size > k) {
      const d = s[left];
      count.set(d, count.get(d) - 1);
      if (count.get(d) === 0) count.delete(d);
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
}

k = 0 的特判别省：收缩循环靠 count.size > k 驱动，k 为 0 时它推不出合法窗口，必须在入口挡住。这个泛化版本同样通过了与暴力基准的 500 轮随机差分。面试里被问「滑动窗口学来干什么」时，这就是最好的答案：本题的解法会过期，模板不会。

顺着这条线可以继续刷的题：

LeetCode 159 至多包含两个不同字符的最长子串：k = 2 的特例，适合当泛化版的第一道练习。
LeetCode 76 最小覆盖子串：窗口题的另一极——求最短而不是最长，收缩发生在「窗口已满足条件」时，方向感与本题相反。
LeetCode 209 长度最小的子数组：把「字符不重复」换成「元素和不超过阈值」，窗口装的对象变了，骨架一字不易。
LeetCode 424 替换后的最长重复字符：窗口内维护「最多字符的计数」，是记计数写法的进阶变体。
LeetCode 1004 最大连续 1 的个数 III：把「翻转 k 个 0」翻成「窗口内至多 k 个 0」，同一模板的又一变身。

参考资料

LeetCode 3. 无重复字符的最长子串（题目页）——本文题面、约束与示例的出处，可在线提交验证。
LeetCode 官方题解：无重复字符的最长子串——官方对暴力、哈希集与滑动窗口的逐步推导，含多语言实现。
LeetCode 340. 至多包含 K 个不同字符的最长子串——延伸问题的原题（会员题），验证模板迁移的第一站。
OI Wiki：双指针与滑动窗口——把本题放回「同向双指针」方法族的系统性梳理。