![在这里插入图片描述](https://developer.qcloudimg.com/http-save/yehe-11543487/b03a8fd20ea803588e5104c058a09080.png)

## 摘要

这道题是 LeetCode 第 3 题「无重复字符的最长子串」，也是国内大厂后端面试中出现次数最多的算法题（累计 1211 次）。题目本身不难，难在容错率极低：输入 `abba` 时，一份看起来完全正确的滑动窗口代码会安静地返回 3 而不是 2。本文从直觉解法讲起，逐步拆解如何把 O(n²) 压到严格的 O(n)，并重点剖析那半行 `last[c] >= left` 守卫判断——它决定了窗口是否会回退、答案是否合法。最后用 20 万次暴力对撞验证三种实现，并附上面试官最可能追问的清单。

---

## 目录

- [一、题目本身没有难度](#一题目本身没有难度)
- [二、直觉解法为什么不够](#二直觉解法为什么不够)
- [三、两个念头，把 O(n³) 压到 O(n)](#三两个念头把-on³-压到-on)
- [四、全部区分度就在那半行判断](#四全部区分度就在那半行判断)
- [五、代码](#五代码)
- [六、我把它跑了 20 万次](#六我把它跑了-20-万次)
- [附：这题的追问清单](#附这题的追问清单)

---



我拉过一份面经聚合数据，想看国内大厂后端面试里出现次数最多的算法题到底是哪道。

答案不是接雨水，不是反转链表。是一道中等难度的字符串题：**无重复字符的最长子串**，LeetCode 第 3 题，累计出现 1211 次，比第二名整整多出 249 次。

高频不稀奇，每年校招总有一批题反复出现。让我想单独写它的原因是另一件事：这道题的容错率极低。

低到什么程度？我在 `aba` 后面再加一个 `b`，也就是输入 `abba`，一份看起来完全正确的滑动窗口代码就会给出错误答案。它不会报错、不会越界、不会进死循环，它只是安静地返回 3 而不是 2，然后把你的面试评价从 A 拉到 B。

我见过太多人能把滑动窗口的定义背得一字不差，却在这道题上少写了半行判断。

那就从头说清楚。

---

## 一、题目本身没有难度

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

注意是子串不是子序列，字符必须连续。`abcabcbb` 的答案是 3（`abc`），`bbbbb` 的答案是 1，`pwwkew` 的答案是 3（`wke`，不是 `pwke`，因为 `pwke` 不连续）。

唯一的门槛是性能：字符串长度上限 5 万，也就是要求线性时间。

---

## 二、直觉解法为什么不够

第一反应通常是双重循环。以每个位置为起点往后扩展，遇到过重复字符就换下一个起点。这个思路完全正确，但复杂度是 O(n²)，5 万的长度下会跑到十亿次量级，必然超时。

第二个反应是「窗口 + 集合」。用两个指针框住一段区间，右指针不断向右扩，把字符塞进集合；一旦发现要塞的字符已经在集合里，就把左指针往右挪，同时把字符从集合里移出去。

这个版本能过。它是对的。

但它不够好，原因在于左指针的移动方式：遇到一次重复，左指针只挪一格；如果重复源在很靠左的位置，它就得一格一格挪很多次。整个过程左指针最坏会移动 n 次，右指针也移动 n 次，复杂度是 O(2n)。

能过，但不漂亮。而且面试官追一句「能不能更快」，这里就卡住了。

---

## 三、两个念头，把 O(n³) 压到 O(n)

从「能过」到「过得好」，其实只需要改变两个念头。

![在这里插入图片描述](https://developer.qcloudimg.com/http-save/yehe-11543487/b1037d8e1f87f981ba49a9f70d95652e.png)

**第一个念头：记什么。**

集合只能回答「这个字符出现过吗」，回答不了「它上次出现在哪」。所以只能一格一格试。

换成哈希表，用字符做键、最后出现的下标做值。这时候原来的问题就变成一句可以直接计算的话：这个字符上次出现的位置，比左指针还靠右吗？

如果是，说明它就在当前窗口里，左指针应该跳到我上次出现的下一位，而不是一格一格挪。一次跳到位，左指针的总移动量仍然是 n，复杂度被压成严格的 O(n)。

**第二个念头：跳多远。**

这一步是很多人翻车的地方，下一节展开。

先看完整的逐帧过程。下面这张图不是手绘示意，是我把解法真实运行起来、把每一步的状态导出后画出来的：

![在这里插入图片描述](https://developer.qcloudimg.com/http-save/yehe-11543487/fe18e7c335c84a067a596d959e03c401.png)


沿着这张图看几步就明白规律了。

前 3 步一路顺利，窗口长到 3。第 4 步读到一个 `a`，而 `a` 在位置 0 出现过，位置 0 就在窗口里，于是左指针跳到 1，窗口变成 `bca`。第 5、6 步同理，每次都触发收缩，窗口长度稳定停在 3。

到第 7 步，读到的字符是 `b`，它上次出现在位置 4。此时左指针在 3 —— 位置 4 仍然在窗口里，所以左指针跳到 5，窗口变成 `cb`。

你会发现右指针从头到尾只往右走，左指针也从头到尾只往右走。两个指针各自最多扫一遍数组，这就是 O(n) 的来源。

---

## 四、全部区分度就在那半行判断

再看第 8 步。读到的还是 `b`，它上次出现在位置 6。这次左指针直接跳到了 7，窗口只剩一个 `b`。

这里有个容易被忽略的细节：位置 6 当时**就在**窗口里吗？

回到第 3 步结束时，左指针是 0。第 6 步收缩后左指针是 3。第 7 步收缩后左指针是 5。位置 6 一直在窗口内，所以第 8 步的收缩是合理的。

但如果重复字符的位置**已经滑出窗口**了呢？这时候它还该不该触发收缩？

不该。可代码里如果只写「这个字符出现过就收缩」，它就会收缩，而且会把左指针往左拉。

我们来看 `abba` 这个用例。

![在这里插入图片描述](https://developer.qcloudimg.com/http-save/yehe-11543487/464c982cd1cdbed34dad914f7ceed383.png)


上半部分是正确写法，下半部分是漏掉判断的写法。

到第 4 步，读入末尾的 `a`。查表得知 `a` 上次出现在位置 0，而此时左指针已经是 2 —— 那个 `a` 早就滑出窗口了。

正确写法在这里什么都不做，窗口是 `ba`，答案 2。

漏判的写法仍然把左指针拉回 1。于是窗口变成 `bba`，里面有两个 `b`，**它已经不是合法子串了**，但代码不知道，它会算出长度 3 并返回。

问题的本质是：左指针回退了。

滑动窗口这个技巧有一个隐含前提，就是窗口只会扩张或收缩，绝不倒退。左指针一旦往左走，窗口里就可能重新包含已经被判定为重复的字符，而代码里没有任何机制能在后续步骤里发现这件事。

守住这条前提的，就是那半行判断：

```java
if (last[c] >= left) {   // 守卫：只在窗口内出现过才收缩
    left = last[c] + 1;
}
```

`last[c] >= left` 的意思是「上次出现的位置没有滑出窗口左边界」。这个条件成立，收缩是安全的；不成立，说明那个字符已经离开了窗口，重复不存在了，什么都不用做。

不是所有错都能用 `abba` 测出来。我顺手试了几个：

| 输入 | 正确答案 | 漏判写法 | 为什么错 |
|---|---|---|---|
| `abba` | 2 | **3** | 左指针从 2 回退到 1，窗口变成 `bba` |
| `tmmzuxt` | 5（`mzuxt`） | **6** | 左指针回退到 1，窗口变成 `mmzuxt` |
| `abccba` | 3 | **5** | 左指针回退到 1，窗口变成 `bccba` |

三个用例的共同点都是「某个字符在很早的位置出现过，之后滑出窗口，末尾又出现了同一字符」。这个形状比 `abba` 更长，但本质一样。

`abba` 只是最短的那个。

---

## 五、代码

主语言给三个版本，逻辑完全一致。

**Java**（面试首选，字符集已知时用定长数组，常数最小）：

```java
public int lengthOfLongestSubstring(String s) {
    int[] last = new int[128];
    Arrays.fill(last, -1);
    int left = 0, ans = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (last[c] >= left) {          // 守卫：只在窗口内出现过才收缩
            left = last[c] + 1;
        }
        last[c] = right;
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}
```

**Go**：

```go
func lengthOfLongestSubstring(s string) int {
	last := [128]int{}
	for i := range last {
		last[i] = -1
	}
	left, ans := 0, 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		if last[c] >= left {
			left = last[c] + 1
		}
		last[c] = right
		if n := right - left + 1; n > ans {
			ans = n
		}
	}
	return ans
}
```

**Python**：

```python
def length_of_longest_substring(s: str) -> int:
    last = {}
    left = ans = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        ans = max(ans, right - left + 1)
    return ans
```

复杂度：时间 O(n)，每个字符被访问常数次；空间 O(min(n, σ))，σ 是字符集大小。

**一个真实存在的坑**：Java 和 Go 版本用 `int[128]`，下标是 ASCII 范围。如果输入含中文，`s.charAt` 拿到的是 UTF-16 码元、Go 的 `s[right]` 拿到的是 UTF-8 字节，都可能超出 127 直接数组越界。线上代码要处理非 ASCII 输入时，退回 `HashMap` 或用 `int[65536]`，别省这点内存。

---

## 六、我把它跑了 20 万次

写完代码我并不放心，尤其是那三个反例是我偶然试出来的，谁知道还有没有别的形状。

所以我让华为云码道（CodeArts 代码智能体）帮我把验证脚本搭起来，思路是拿一个绝对正确的暴力解当基准，和优化解对撞。

暴力解的写法笨到不可能错：枚举所有起点，从每个起点往后扫，用布尔数组记录遇到过的字符，撞到重复就停。复杂度 O(n²)，正确性一眼可见。

然后这样跑：

- **穷举对撞**：把字母表 `{a,b}` 上长度不超过 10、字母表 `{a,b,c}` 上长度不超过 7 的所有字符串全部生成出来，逐个比对。共 **5327 个用例**。
- **随机对撞**：字母表从 `ab`（强制高频重复）到 26 个字母、到含空格的符号集，长度 0 到 400，跑 **200000 个随机用例**。

三种优化实现——定长数组版、`HashMap` 版、以及那个「一格一格缩」的集合版——与暴力解的比对结果是 **0 处不一致**。

顺便把漏判版本也塞进去一起跑，它在这三组数据上错了：

```
solBug wrong on [abba]:    got 3, correct 2
solBug wrong on [tmmzuxt]: got 6, correct 5
solBug wrong on [abccba]:  got 5, correct 3
```

这就是为什么我说 `abba` 只是最短的那个反例，而不是唯一的那个。如果面试官想确认你是不是真懂，他们有权换一个更长的输入来问。

跑完之后，我也顺手把这份脚本里两个细节写进了自己的笔记：一个是 `abba` 必须单独放进回归用例集，因为它是最小的守卫缺失触发器；另一个是字母表只取 `{a,b}` 的穷举特别有效，重复频率高，能在一千个用例内就暴露出边界问题。

---

### 附：这题的追问清单

面试官在这道题上能追问的东西不多，但每一条都指向同一个地方。

| 追问 | 想确认什么 | 怎么答 |
|---|---|---|
| 为什么 `left` 不回退？ | 你是否理解窗口的单调性 | 回退会让窗口重新包含已判定的重复字符，且后续没有任何步骤能纠正；窗口的合法性只能靠单调推进来保证 |
| `abba` 你的代码对吗？ | 你是否真的写过、跑过 | 现场推一遍第 4 步，指出 `last[a]=0 < left=2`，守卫拦下 |
| 输入含中文怎么办？ | 你有没有线上意识 | 说清 `int[128]` 的越界风险，退回 `HashMap` 或 `int[65536]` |
| 变体：最多允许 K 次重复呢？ | 能不能迁移 | 把「出现过」改成「出现次数超过 K」，窗口收缩条件随之变化 |
| 变体：最长重复字符替换后？ | 是否只会套模板 | 那是另一道题（LC 424），收缩时机不同，别硬套 |

最后一条其实最关键。`left` 什么时候该动，是滑动窗口类题目的统一命题，而每一道题的答案都不一样。这道题考的不是你记不记得模板，是你知不知道为什么要在这里动它。

---

**金句**：滑动窗口从来不是一种技巧，它是一个承诺——窗口只往前走，绝不回头。写漏那半行判断的人，亲手打破的正是这个承诺。

---

下一篇想聊第 2 名：LRU 缓存。它在同一份数据里出现了 962 次，是唯一挤进前两名的设计题。有意思的是，面试官几乎一定会接着问「你的 `get` 加了什么锁」——而正确答案是写锁，不是读锁。为什么，我们下篇说。

这道题是 LeetCode 第 3 题「无重复字符的最长子串」，也是国内大厂后端面试中出现次数最多的算法题（累计 1211 次）。题目本身不难，难在容错率极低：输入 abba 时，一份看起来完全正确的滑动窗口代码会安静地返回 3 而不是 2。本文从直觉解法讲起，逐步拆解如何把 O(n²) 压到严格的 O(n)，并重点剖析那半行 last[c] >= left 守卫判断——它决定了窗口是否会回退、答案是否合法。最后用 20 万次暴力对撞验证三种实现，并附上面试官最可能追问的清单。

面试出现 1211 次的算法题：一行判断写错就归零

这道题是 LeetCode 第 3 题「无重复字符的最长子串」，也是国内大厂后端面试中出现次数最多的算法题（累计 1211 次）。题目本身不难，难在容错率极低：输入 abba 时，一份看起来完全正确的滑动窗口代码会安静地返回 3 而不是 2。本文从直觉解法讲起，逐步拆解如何把 O(n²) 压到严格的 O(n)，并重点剖析那半行 last[c] >= left 守卫判断。

程序员

算法

后端

职业发展

无重复字符最长子串是LeetCode第3题，国内大厂面试高频（1211次），核心难点在于滑动窗口左指针的守卫判断last[c]>=left，防止回退导致错误结果。本文提供O(n)解法，通过abba等反例验证，并附20万次对撞测试及面试追问清单，确保代码正确性与理解深度。

代码解释

智能体

Python

Java

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

面试出现 1211 次的算法题：一行判断写错就归零-腾讯云开发者社区-腾讯云

面试出现 1211 次的算法题：一行判断写错就归零

面试出现 1211 次的算法题：一行判断写错就归零

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐