力扣hot100滑动窗口（C++）

一、无重复字符的最长子串

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

1.1题目解析

这道题要求找到一个字符串中不包含重复字符的最长子串的长度。子串必须是连续的字符序列，不是子序列，不能跳着选字符。

1.2初试

我最开始的想法很简单：把每个可能的子串都检查一遍。从字符串的第一个字符开始，看看能往右延伸多远不出现重复字符，记录这个长度，然后从第二个字符开始同样检查，一直试完所有起始位置。

class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); if(n == 0) return 0; int maxlength = 1; for(int i = 0; i < n; i++) { int a[256] = {0}; // 用数组记录字符出现次数 for(int j = i; j < n; j++) { int k = (int)s[j]; // 字符转成ASCII码值 a[k]++; if(a[k] == 2) { // 某个字符出现两次，说明有重复 maxlength = max(maxlength, j - i); break; } maxlength = max(maxlength, j - i + 1); } } return maxlength; } };

这个方法很直观，但效率太低。外层循环遍历每个起始位置，内层循环从起始位置向右延伸检查重复。对于长度为n的字符串，最坏情况下要检查n²/2个子串，时间复杂度是O(n²)。当字符串很长时，这个算法会超时。

1.3优化思路：滑动窗口

注意到暴力解法中有很多重复计算：比如检查从i到j的子串没有重复后，检查从i到j+1的子串时，其实只需要判断s[j+1]这个字符是否在前面出现过，不需要重新检查整个子串。

如果用滑动窗口的方法，维护一个窗口，窗口里的字符都是不重复的。右指针不断向右扩展窗口，当遇到重复字符时，左指针向右移动直到窗口内没有重复字符。

int lengthOfLongestSubstring(string s) { unordered_map<char, int> charIndex; // 记录每个字符最近出现的位置 int n = s.size(); int maxlength = 0; int left = 0; // 窗口左边界 for(int right = 0; right < n; right++) { // 如果当前字符已存在且在窗口内 if(charIndex.count(s[right]) && charIndex[s[right]] >= left) { left = charIndex[s[right]] + 1; // 左边界跳到重复字符的下一位 } charIndex[s[right]] = right; // 更新字符位置 maxlength = max(maxlength, right - left + 1); // 更新最大长度 } return maxlength; }

这个算法的关键是用哈希表记录每个字符最近出现的位置。右指针一直向右移动，左指针只有遇到重复字符时才移动。这样每个字符最多被访问两次（右指针一次，左指针一次），时间复杂度降到O(n)。

这里有个细节要注意：判断字符是否在窗口内时，不仅要看这个字符是否出现过，还要看它最近出现的位置是否在left的右边。因为字符可能在窗口外面出现过，这种重复不影响当前窗口。

二、 找到字符串中所有字母异位词

（s和p只包含小写字母）

2.1题目解析

这道题要在字符串s中找到所有是p的异位词的子串，返回这些子串的起始索引。异位词指的是字母相同但顺序可以不同的词，比如"abc"和"bca"是异位词。

2.2初试

看到这道题，我觉得很适合用滑动窗口，因为要找的是固定长度的子串。窗口长度就是p的长度，我们需要检查每个这个长度的窗口是否是p的异位词。

class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> result; if(s.length() < p.length()) return result; // s比p短，不可能有异位词 // 记录p中每个字符的出现次数 vector<int> pCount(26, 0); for(char c : p) { pCount[c - 'a']++; } // 记录窗口内字符的出现次数 vector<int> windowCount(26, 0); int windowSize = p.length(); // 初始化第一个窗口 for(int i = 0; i < windowSize; i++) { windowCount[s[i] - 'a']++; } // 检查第一个窗口 if(windowCount == pCount) { result.push_back(0); } // 滑动窗口 for(int i = windowSize; i < s.length(); i++) { // 移除窗口左边字符 windowCount[s[i - windowSize] - 'a']--; // 添加窗口右边新字符 windowCount[s[i] - 'a']++; // 检查当前窗口是否是异位词 if(windowCount == pCount) { result.push_back(i - windowSize + 1); } } return result; } };

这个方法维护一个固定长度的窗口，每次滑动时更新窗口内字符计数，然后比较窗口计数和p的计数是否相同。时间复杂度是O(n)，空间复杂度是O(1)（因为只有26个小写字母）。

2.3进一步优化

上面的方法需要每次都比较两个26位的数组，虽然常数时间，但还可以优化。可以用一个变量记录窗口和p的差异程度。

vector<int> findAnagrams(string s, string p) { vector<int> result; int sLen = s.length(), pLen = p.length(); if(sLen < pLen) return result; vector<int> count(26, 0); // 初始化：p中的字符加1，窗口中的字符减1 // 这样如果count中某个字符为0，表示这个字符在p和窗口中数量相同 for(int i = 0; i < pLen; i++) { count[p[i] - 'a']++; count[s[i] - 'a']--; } int diff = 0; // 记录有多少个字符的数量不匹配 for(int num : count) { if(num != 0) diff++; } if(diff == 0) result.push_back(0); // 滑动窗口 for(int i = pLen; i < sLen; i++) { char leftChar = s[i - pLen] - 'a'; char rightChar = s[i] - 'a'; // 移除左边字符 if(count[leftChar] == 0) diff++; // 原来匹配，现在移除后不匹配了 count[leftChar]++; if(count[leftChar] == 0) diff--; // 现在又匹配了 // 添加右边字符 if(count[rightChar] == 0) diff++; // 原来匹配，现在添加后不匹配了 count[rightChar]--; if(count[rightChar] == 0) diff--; // 现在又匹配了 if(diff == 0) result.push_back(i - pLen + 1); } return result; }

这个优化的好处是不用每次比较两个数组，只需要维护一个diff变量，表示有多少个字符在窗口和p中数量不同。当diff为0时，窗口就是p的异位词。每次窗口滑动时，只需要更新移出字符和移入字符对diff的影响。

三、算法特点总结

滑动窗口算法特别适合处理连续子串或子数组问题。它的核心思想是维护一个窗口，通过移动窗口的左右边界来遍历所有可能的子串/子数组，同时高效地更新窗口状态。

3.1窗口的三种类型：

• 固定长度窗口：像第二题，窗口长度固定为p的长度，每次滑动一个位置检查
• 可变长度窗口：像第一题，窗口长度根据条件变化，右指针扩展窗口，左指针在条件不满足时收缩窗口
• 多指针窗口：有些复杂问题可能需要多个指针协同工作

3.2滑动窗口的优点：

• 通常能将O(n²)的暴力解法优化到O(n)
• 思路清晰，代码结构统一
• 适合处理连续区间问题

写在最后

滑动窗口是一个很实用的技巧，掌握后能解决很多字符串和数组问题。关键是多练习，理解不同问题中窗口的含义和移动规则。

如果还有其他想法的小伙伴可以在评论区积极讨论。