LeetCode 3. 无重复字符的最长子串 | C 滑动窗口双解法题解 题目描述题目级别中等给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例 1:输入:s abcabcbb输出: 3解释: 因为无重复字符的最长子串是abc所以其长度为 3。示例 2:输入:s pwwkew输出: 3解释: 因为无重复字符的最长子串是wke所以其长度为 3。请注意你的答案必须是子串的长度pwke是一个子序列不是子串。 解题思路滑动窗口 (Sliding Window)寻找连续的子串最优雅的解法就是滑动窗口。我们可以用两个指针l左边界和r右边界来维护一个“窗口”这个窗口内的所有字符都保证是不重复的。核心步骤窗口扩张吃进字符右指针r负责在前面开路每次遍历都将新字符纳入窗口。窗口收缩吐出字符在纳入新字符之前我们需要检查这个字符是否已经在窗口里出现过了。如果出现了说明遇到了“重复字符”窗口不再合法。此时左指针l必须开始向右移动把以前吃进去的字符一个一个吐出来直到把那个和新字符重复的“罪魁祸首”踢出窗口。记录最大值每次窗口恢复合法状态无重复字符后当前窗口的长度就是r - l 1。我们在这个过程中不断刷新最大长度记录即可。 解法一使用 unordered_set (标准通用解法)在判断字符是否重复时最直观的方法是使用哈希集合。注意在 C 中强烈建议使用unordered_set而不是set。因为set底层是红黑树时间复杂度O(log⁡N)O(\log N)O(logN)而unordered_set底层是哈希表单次查找和插入的时间复杂度为O(1)O(1)O(1)。 C 代码实现classSolution{public:intlengthOfLongestSubstring(string s){unordered_setcharus;// 记录窗口内出现的字符intl0,res0;for(intr0;rs.size();r){// 如果即将吃进来的字符 s[r] 已经在窗口里了// 左指针 l 就必须右移边移动边从 set 中抹除记录直到踢出重复字符while(us.count(s[r])){us.erase(s[l]);l;}// 将新字符纳入窗口us.insert(s[r]);// 刷新最长子串的记录resmax(res,r-l1);}returnres;}}; 解法二使用布尔数组 (极致性能优化版)由于题目中的字符通常只是 ASCII 码总共只有 128 个可能的值。我们可以直接用一个大小为 128 的布尔数组来代替哈希表。优势数组的内存地址是连续的且通过下标访问没有任何哈希函数的计算开销速度比 unordered_set 还要快得多是真正意义上的极致O(1)O(1)O(1)。 C 代码实现classSolution{public:intlengthOfLongestSubstring(string s){// 使用大小为 128 的布尔数组代替 unordered_set极大地提升常数时间性能boolhash[128]{false};intl0,res0;for(intr0;rs.size();r){// 遇到重复字符左指针收缩while(hash[s[r]]){hash[s[l]]false;l;}// 标记当前字符已在窗口内hash[s[r]]true;// 刷新最长子串的记录resmax(res,r-l1);}returnres;}};