LeetCode 3：无重复字符的最长子串（滑动窗口） —— 题解

👋 欢迎阅读

一.题目

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

​

🎯 欢迎来到「无重复字符的最长子串」题解之旅！本文将带你从“寻找不含重复字符的最长连续片段”这一经典字符串问题出发，深入理解滑动窗口（双指针）的灵活应用，并掌握如何通过哈希表（或数组模拟）高效维护窗口内字符的唯一性。

在开始之前，建议你先：

• 了解题目背景：这是 LeetCode 3 题，给定字符串s，要求找出不含重复字符的最长子串的长度（注意是连续子串，不是子序列）。本质上是动态维护一个窗口，保证窗口内所有字符互不相同，并在扩展和收缩过程中记录窗口的最大长度。

• 明确学习目标：掌握滑动窗口核心操作——右指针持续向右扩展，每加入一个新字符就检查是否重复；若重复，则移动左指针，将重复字符及其之前的字符全部移出窗口（直至窗口内无重复）。理解如何利用哈希表记录字符最新出现位置（或数组计数）来快速判断重复，并熟练实现双指针扫描 + 更新最大长度的代码逻辑。

• 准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如s = "abcabcbb"输出3，s = "pwwkew"输出3）。

本文将从问题转化、滑动窗口策略设计（右扩左缩）、重复判定与窗口维护到代码实现，层层递进。即使你对滑动窗口还不熟悉，我们也会从“用一个窗口框住不重复的字符，大了就缩，小了就扩”这一直觉出发，让你轻松抓住核心思想——窗口内字符唯一是约束条件，窗口大小是优化目标，双指针负责动态调整。现在，让我们一起在字符串中滑动窗口，找出那个最长的不重复片段吧！ 📝🔍

二.做题思路

一、问题分析（前置分析）

给定一个字符串s，要求找出不含重复字符的最长子串的长度。
核心观察：当窗口内出现重复字符时，只需要移动左指针跳过重复字符，右指针无需回退。这是滑动窗口的典型应用，可在 O(n) 时间内解决。

二、算法策略（滑动窗口 + 哈希表）

• 使用哈希表（数组模拟）记录当前窗口内每个字符的出现次数（值为 0 或 1，因为窗口内不能有重复）。

• 右指针right不断向右扩展，每加入一个字符就增加其计数。

• 若当前加入的字符出现次数 ≥ 2，说明窗口内有重复，此时需要移动左指针left，将重复字符从窗口中移除（计数置 0），直到窗口再次无重复。

• 在窗口有效期间，不断更新最长无重复子串的长度。

示例执行过程（s = "abcabcbb"）：

最终结果为 3，对应子串"abc"、"bca"或"cab"。

三、正确性说明（简单版本）

滑动窗口维护了一个无重复字符的窗口。每次右指针扩展时，若新字符导致重复，则移动左指针直到重复消失。因为右指针从不回退，每个字符最多被加入和移除窗口各一次，所以能遍历所有可能的无重复子串。在窗口有效的每个时刻，当前窗口都是以right为右端点的最长无重复子串，因此更新最大长度即可得到全局最优解。

四、实现细节（边界防护）

• 使用int hash[128] = {0}记录 ASCII 字符出现次数（0 或 1）。

• 外层for循环中right的更新在循环体内手动控制，需注意边界。

• 当hash[s[right]] == 1时（即新字符已存在），进入while循环：

  • hash[s[left]] = 0（移出窗口）；

  • left++；

  • 继续检查直到窗口内无重复。

• 每次窗口有效时，更新len = max(len, right - left + 1)。

• 注意空字符串处理：若n == 0，直接返回 0。

• 时间复杂度 O(n)，空间复杂度 O(1)（哈希表大小固定为 128）。

五、返回值（目标映射）

返回len，即最长不含重复字符的子串长度。

三.代码

#include <iostream> #include <string> #include <algorithm> using namespace std; class Solution { public: int lengthOfLongestSubstring(string s) { // 算法思路：滑动窗口 + 哈希表（数组模拟） // 使用 hash 数组记录当前窗口内每个字符出现的次数（0或1，因为窗口内不能有重复字符） // 右指针 right 不断向右扩展窗口，每加入一个字符就增加其计数； // 如果某个字符计数 >= 2，说明窗口内出现重复，此时移动左指针 left，将重复字符从窗口中移除。 // 在窗口有效（无重复）期间，不断更新最长无重复子串的长度。 int hash[128] = {0}; // 哈希表，用于记录 ASCII 字符在当前窗口中的出现次数（值 0 或 1） int n = s.size(); int len = 0; // 记录当前找到的最长无重复子串长度 // 双指针：left 和 right 定义当前窗口 [left, right] // 注意：外层 for 循环中 left 和 right 的更新逻辑略复杂，但本质仍是滑动窗口 for (int left = 0, right = 0; right < n; ) { // 入窗口：将 s[right] 加入窗口，计数加1 hash[s[right]]++; // 当窗口内没有重复字符时（即当前新加入的字符出现次数小于2），持续扩展右指针 while (right < n && hash[s[right]] < 2) { // 更新最长无重复子串长度（当前窗口长度为 right - left + 1） len = max(len, right - left + 1); // 右指针右移，继续扩展窗口 right++; // 注意：这里再次执行入窗口操作，将新字符加入窗口 // （第一次入窗口在循环开始处，但 right 移动后需要对新位置进行计数） // 这种写法略显冗余，但保证了逻辑完整性 if (right < n) { hash[s[right]]++; } } // 如果因为 right 越界或出现重复字符而退出 while 循环， // 则说明当前窗口无法继续扩展（或已到末尾）。 // 此时需要将左指针指向的字符移出窗口（将计数置0）， // 然后左指针右移，尝试缩小窗口以消除重复。 hash[s[left]] = 0; // 将 left 指向的字符从窗口中移除（计数重置为0） left++; // 左指针右移 } // 返回最长无重复子串的长度 return len; } }; int main() { // 测试用例：字符串 "abcabcbb"，最长无重复子串是 "abc"，长度为 3 string s = "abcabcbb"; Solution sol; int result = sol.lengthOfLongestSubstring(s); cout << result << endl; // 输出 3 return 0; }

四、易错点分析

难点一：len的更新时机与窗口有效性的关系

while (right < n && hash[s[right]] < 2) { len = max(len, right - left + 1); right++; // ... }

难点：只有窗口内无重复字符时（即hash[s[right]] < 2），才更新len。一旦出现重复，循环终止，不会更新长度，因为此时的窗口是无效的。
这要求必须理解：len只在窗口“干净”的时候被记录，而left的移动则是为了重新使窗口变干净。因此，更新长度和移动左指针是两个独立阶段，顺序不能颠倒。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「无重复字符的最长子串」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

• 本题使用滑动窗口维护一个无重复字符的区间，右指针不断扩展，当出现重复字符时移动左指针。请问为什么滑动窗口能保证找到最长无重复子串？其核心逻辑是什么？

• 代码中使用了hash[128]数组来记录字符出现次数。为什么数组大小是 128 而不是 256？如果字符串包含中文或其他 Unicode 字符，这种方式还适用吗？

• 当发现重复字符时（hash[s[right]] >= 2），代码将hash[s[left]] = 0并left++，直接清空了左指针指向的字符计数。如果窗口内该字符出现了多次，这样的清空方式是否会导致计数错误？请结合具体例子说明。

• 代码中的while循环在right未越界且hash[s[right]] < 2时不断扩展，这种写法与常见的for循环滑动窗口有何异同？哪种更易理解？

• 本题时间复杂度为O(n)，因为每个字符最多被左右指针各访问一次。如果字符串长度n = 10^5，这个算法是否高效？空间复杂度如何？

📚延伸挑战

• 如果要求返回最长无重复子串本身（而不是长度），代码应做哪些调整？

• 如果字符集非常大（如 Unicode 全部字符），不能使用固定数组模拟哈希表，你会改用哪种数据结构？请说明修改方案。

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

• 滑动窗口的核心是保证窗口内始终无重复字符，一旦出现重复，就移动左指针直到重复消失。这样每个以right结尾的最长无重复子串都会被考虑到，因此不会遗漏最优解。

• 数组大小 128 覆盖了标准 ASCII 字符集（0~127），如果字符串包含中文等 Unicode 字符，编码值会超过 127，数组越界。此时应改用unordered_map<char, int>或vector<int>(256)（若只考虑扩展 ASCII 则用 256）。

• 清空计数的方式有风险：例如窗口内有两个相同字符a，hash['a']可能为 2，但代码hash[s[left]] = 0会将计数直接置 0，而实际上窗口中可能还剩一个a。这种写法依赖于每次发现重复时立即移动左指针，直到重复消失，但这里只移了一位就置 0，会导致窗口状态错误。更好的写法是hash[s[left]]--（减 1）而不是置 0。当前代码之所以能运行，是因为每次发现重复后只移动一次左指针，但若重复字符在窗口内出现多次，这种方法会出错（例如"abca"中窗口"abca"出现重复a，左指针移过第一个a后，窗口变为"bca"，计数中a已清零，但b和c仍保留，逻辑是通的，因为hash[s[left]] = 0只清除了被移出的字符，而a在窗口中已不再存在，所以正确）。因此该写法是安全的，因为每次只移除一个确定的左边界字符，该字符在窗口中只出现一次（由于窗口内本应无重复，重复只发生在刚加入的right上，而左指针逐步右移，被移除的字符在窗口中确实只有一次出现）。

• 两种写法本质相同，常见的for循环写法更简洁：外层right++，内层while收缩左指针，可读性更好。

• O(n) 时间，O(1) 空间（固定哈希数组），对于n=10^5非常高效，完全可接受。

🔍延伸挑战答案

• 挑战1：若要返回子串本身，只需在更新len的同时记录起始下标start，最后返回s.substr(start, len)即可。

• 挑战2：改用unordered_map<char, int>存储字符及其最新出现位置，或使用unordered_set<char>配合滑动窗口，空间复杂度变为 O(字符种类数)，可处理任意 Unicode 字符。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨