LeetCode 第3题《无重复字符的最长子串》笔记

一、题目回顾

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

示例：

• 输入：s = "abcabcbb"

• 输出：3

• 解释：因为无重复字符的最长子串是"abc"，所以长度为 3。

提示：

• 0 <= s.length <= 5 * 10^4

• s由英文字母、数字、符号和空格组成

二、核心知识点

知识点1：滑动窗口的核心思想

滑动窗口是处理子串问题的经典方法，用两个指针（左、右）维护一个动态窗口。

• 右指针 (right)：负责向右扩展，将新字符加入窗口。

• 左指针 (left)：负责在发现重复时，将窗口左侧收缩到重复字符之后。

• 核心目标：始终保证窗口内所有字符不重复，并记录窗口长度的最大值。

形象理解：想象一个可以伸缩的“窗口”在字符串上滑动，右边界不断尝试扩大，左边界在遇到重复时向右收缩。

知识点2：关键数据结构last_pos数组

作用：快速查询一个字符是否在窗口内，以及它上一次出现的位置。

定义：int last_pos[128];

存储逻辑：

• 下标：字符的 ASCII 码值（例如'a'的 ASCII 码是 97）。

• 值：该字符最后一次出现的位置索引。

• 初始值设为-1，表示该字符从未出现。

为何固定128：足以覆盖所有标准 ASCII 字符，空间开销极小（512字节）。

图解存储结构：

字符: a b c d e ... z ASCII: 97 98 99 100 101 ... 122 last_pos数组： 索引: 0 1 2 ... 97 98 99 100 ... 127 [ ][ ][ ] [3 ][5 ][2 ][-1 ] [ ] 不 不 不 'a' 'b' 'c' 'd' 用 用 用 的 的 的 的 值 值 值 值

知识点3：核心判断逻辑last_pos[ch] >= left

问题：为什么这一句就能判断字符ch是否重复？

解答：它判断的是字符ch上一次出现的位置是否在当前窗口内。

• last_pos[ch]：字符ch上一次出现的位置。

• left：当前窗口的左边界。

• 当前窗口范围是[left, right]。

判断逻辑：

• 若last_pos[ch] >= left→ 该字符的上次出现位置在窗口内 →重复！

• 若last_pos[ch] < left→ 该字符的上次出现位置已被移出窗口 →不重复，可以安全加入。

图解三种情况：

情况1：字符在窗口内（重复）

字符串: a b c a b 索引: 0 1 2 3 4 [===窗口===] left=1, right=3 要加入 right=4 的 'b' last_pos['b'] = 1 (在索引1) 判断：1 >= left(1)? 是！✅ → 重复了！

情况2：字符不在窗口内（不重复）

字符串: a b c a b 索引: 0 1 2 3 4 [===窗口===] left=2, right=3 要加入 right=4 的 'b' last_pos['b'] = 1 (在索引1) 判断：1 >= left(2)? 否！❌ → 没重复！

知识点4：窗口滑动操作（处理重复的步骤）

当遇到重复字符ch时，执行以下三步：

1. 移动左指针：left = last_pos[ch] + 1;（直接跳到重复字符的下一个位置，保证新窗口无重复）。

2. 更新位置：last_pos[ch] = right;（将ch的最新位置更新为当前位置）。

3. 更新最大长度：max_len = max(max_len, right - left + 1);

图解执行过程（以s = "abcabcbb"为例）：

第4步：right=3, ch='a', last_pos['a']=0, left=0 发现重复！left从0跳到1 窗口从 [a,b,c] 变为 [b,c,a] 第5步：right=4, ch='b', last_pos['b']=1, left=1 发现重复！left从1跳到2 窗口从 [b,c,a] 变为 [c,a,b]

知识点5：为什么你的初步想法需要修正？

你的初步想法：

“从第一个开始，遇到重复就截止，然后从这个重复出现的最后一个开始接着计数。”

问题与修正：

• 这个想法接近滑动窗口，但移动方式有误。

• 不应从“重复的最后一个”开始，而应从重复字符第一次出现位置的下一个位置开始，即left = last_pos[ch] + 1。

• 这样才能保证新窗口内不再包含重复字符。

举例说明：

s = "abca" 正确做法：遇到第二个'a'时，left从0跳到1，窗口变为 [b,c,a] 你的做法：从第二个'a'开始，窗口为 [a]，漏掉了 [b,c,a]

三、常见错误总结

错误1：只检查相邻字符

• 错误写法：if (s[i] == s[i-1])

• 问题分析：只能发现像"aa"这种紧挨着的重复，无法发现"abca"中相距较远的重复字符'a'。

• 正确做法：必须用last_pos数组检查所有出现过的字符，判断其是否在当前窗口内。

错误2：左指针移动方式错误

• 错误写法：left++;（一次只移动一位）

• 问题分析：窗口内可能仍然存在其他重复字符，效率低且容易出错。例如"abcb"中遇到第二个'b'时，left应跳到2，而不是1。

• 正确做法：应直接跳跃到重复字符的下一个位置：left = last_pos[ch] + 1;

错误3：获取字符串长度方式错误

• 错误写法：int len = sizeof(s);

• 问题分析：当s是函数参数（指针）时，sizeof(s)获取的是指针本身的大小（在64位系统上是8字节），而不是字符串长度。

• 正确做法：使用int len = strlen(s);（需要包含#include <string.h>）。

错误4：last_pos数组未初始化

• 错误写法：int last_pos[128];直接使用

• 问题分析：数组初始值为随机值（内存中的垃圾数据），会导致last_pos[ch]判断错误，程序行为不可预测。

• 正确做法：必须将所有元素初始化为-1，表示所有字符都未出现。可以用循环或memset(last_pos, -1, sizeof(last_pos));。

四、完整解题模板

int lengthOfLongestSubstring(char* s) { int len = strlen(s); //计算字符串长度 if (len == 0) return 0; int left = 0; int max_len = 0; int last_pos[128]; // 128个位置，对应128个ASCII字符 // 初始化为-1 for (int i = 0; i < 128; i++) { last_pos[i] = -1; } //滑动窗口主程序 for (int right = 0; right < len; right++) { char ch = s[right]; //判断重复并移动左指针 if (last_pos[ch] >= left) { left = last_pos[ch] + 1; } //更新位置和最大长度 last_pos[ch] = right; int cur_len = right - left + 1; if (cur_len > max_len) { max_len = cur_len; } } return max_len; }

代码要点：

• last_pos数组大小固定为128，适用于所有ASCII字符。

• 左指针left只向右移动（从不回退），保证了 O(n) 的时间复杂度。

• 每次循环都更新max_len，确保记录历史最大值。

五、复杂度分析