力扣热题100—滑动窗口（c++）

3.无重复字符的最长子串

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

    unordered_set<char> charSet; // 用于保存当前窗口的字符int left = 0; // 窗口左指针int maxLength = 0; // 最长子串的长度for (int right = 0; right < s.size(); right++) {// 不断扩大右指针，如果字符重复则收缩左指针while (charSet.find(s[right]) != charSet.end()) {charSet.erase(s[left]);left++;}charSet.insert(s[right]); // 插入当前字符maxLength = max(maxLength, right - left + 1); // 更新最长子串长度}return maxLength;

438.找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

        vector<int> result;if (s.empty() || p.empty() || s.size() < p.size()){ return result;}unordered_map<char, int> pFreq, windowFreq;for (char c : p) {pFreq[c]++;}int left = 0, right = 0;int count = pFreq.size(); // p中不同字符的个数while (right < s.size()) {// 如果当前字符在p中，则更新窗口频率if (pFreq.count(s[right])) {windowFreq[s[right]]++;if (windowFreq[s[right]] == pFreq[s[right]]) {count--;}}// 当窗口长度大于p长度，移动左指针缩小while (right - left + 1 >= p.size()) {if (count == 0) {result.push_back(left);}if (pFreq.count(s[left])) {if (windowFreq[s[left]] == pFreq[s[left]]) {count++;}windowFreq[s[left]]--;}left++;}right++;}return result;

滑动窗口定义

滑动窗口是一种用于处理数组/字符串子区间问题的高效算法技巧，通过维护一个动态的窗口（通常是连续的区间），在遍历数据时调整窗口的左右边界，避免重复计算，从而将时间复杂度优化至 O(n)。

核心思想：

1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。

2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。

3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。

4、重复第 2 和第 3 步，直到 right 到达序列的尽头。