数据结构与算法｜算法总结

之前在用golang二刷代码随想录的时候，遇到209.长度最小的子数组竟然没想到应该用滑动窗口解题！怒而猛刷，并结合各个博客和视频总结滑动窗口题型和模板如下
参考资料：
【精心总结滑动窗口代码模板, 直接搞定80道Leetcode算法题】
【两分钟搞懂滑动窗口算法，致敬3b1b】
【labuladong算法笔记】

再次强调，主要是体会滑动窗口的核心思想，模板只是辅助。

文章目录

滑动窗口的使用场景
滑动窗口的核心思想
- 使用思路（寻找最长）
- 使用思路（寻找最短）
- 模板
- 典型题型推荐
- - 209. 长度最小的子数组
  - 3. 无重复字符的最长子串
  - - set
    - map
    - 使用数组优化哈希表
  - 438. 找到字符串中所有字母异位词
  - - 数组优化
  - 76. 最小覆盖子串

滑动窗口的使用场景

很多题目都是找到所谓的子串、子数组、序列等等
有一些要求：最长、最小、重复等等
条件上的要求满足：串联、覆盖、有无重复、结算结果、出现次数、同时包含XX

一旦出现以上关键词，我们就应该考虑是否能考虑滑动窗口进行解答。

总而言之我认为，它往往是求一个连续的子序列，然后这个子序列要满足某种条件，这种题滑动窗口肯定是可以做的。

滑动窗口的核心思想

滑动窗口一般有几个核心组件：

左右指针构成一个窗口
一般是首先移动右指针，然后判断当前窗内是否满足要求，满足要求存储结果，如果不满足要求了，就开始移动左指针，以求重新满足要求，当左右指针重合，可以认为是满足要求的特殊情况，重新开始移动右指针。
需要一个容器来存储结果
一般是直接定义一个int整型数，在活动窗口中如果满足要求，将结果存储到容器中。

当右指针都到达末尾的时候，即整个流程结束

使用思路（寻找最长）

核心：左右双指针(L, R)在起始点，R向右逐位滑动
每次滑动过程中：
if : 窗口内元素满足条件，R向右扩大窗口，并更新最优结果
if : 窗口内元素不满足条件，L向右缩小窗口
流程结束：R指针到达结尾，整个流程结束

使用思路（寻找最短）

核心：左右双指针(L, R)在起始点，R向右逐位滑动
每次滑动过程中：
if : 窗口内元素满足条件，L向右缩小窗口，并更新最优结果
if : 窗口内元素不满足条件，R向右扩大窗口
流程结束：R指针到达结尾，整个流程结束

模板

两种情况在代码实现中最大的区别就是：内循环中，一个是result不满足要求；一个是当result满足要求！
最长(大)模板

初始化left, right, result, bestResult
某些时候可能需要合适的容器来承载result和bestResult
个人觉得最常用的就是哈希(包括数组、map、set)
while (右指针没有到结尾) {
	窗口扩大，加入right对应元素，更新当前result
	while/if (result不满足要求) {
		窗口缩小，移除left对应元素，left右移
	}
	更新最优结果bestResult
	right++
}
返回bestResult;

这里while/if的区别主要在于如何移动指针，是逐步缩小窗口，还是直接开始新的窗口更新。
最短(小)模板

初始化left, right, result, bestResult
某些时候可能需要合适的容器来承载result和bestResult
个人觉得最常用的就是哈希(包括数组、map、set)
while (右指针没有到结尾) {
	窗口被扩大，加入right对应元素，更新当前result
	while/if (result满足要求) {
		窗口缩小，移除left对应元素，left右移
	}
	更新最优结果bestResult
	right++
}
返回bestResult;

典型题型推荐

以下为最经典的题型：来自代码随想录和LeeCode hot100

209. 长度最小的子数组
3. 无重复字符的最长子串
438. 找到字符串中所有字母异位词
76. 最小覆盖子串

209. 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int right = 0, left = 0;
        int curSum = 0;
        int bestResult = INT_MAX;  // 使用INT_MAX来表示无效的大数，方便之后取最小值

        while (right < nums.size()) {
            curSum += nums[right];  // 扩展窗口右边界
            while (curSum >= target) {
                bestResult = min(bestResult, right - left + 1);  // 更新最短长度
                curSum -= nums[left];  // 缩小窗口
                left++;  // 正确的是left增加
            }
            right++;  // 继续向右扩展窗口
        }

        return bestResult == INT_MAX ? 0 : bestResult;  // 如果没有更新过bestResult，返回0
    }
};

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

本题最核心的就是选一个容器来装字符：

set

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;  // 用于存储窗口中的字符
        int left = 0, right = 0;  // 双指针，表示当前的滑动窗口[left, right)
        int bestResult = 0;       // 最长无重复字符的子串长度

        while (right < s.length()) {
            char rChar = s[right];  // 右指针对应的字符
            // 如果字符已经存在于set中，移动左指针直到移除重复字符
            while (set.find(rChar) != set.end()) {
                set.erase(s[left]);
                left++;
            }
            // 添加新字符到set中，更新结果，移动右指针
            set.insert(rChar);
            bestResult = max(bestResult, right - left + 1);
            right++;
        }

        return bestResult;
    }
};

map

第一反应是使用unordered_map，我们可以在map中key为出现的字符，value为该字符的下标，方便左边的更新，下边的数组优化方案也是一样的道理，所以并这类题并不需要循环

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;  // 字符到其最近出现位置的映射
        int left = 0, right = 0;       // 双指针，表示当前的滑动窗口[left, right)
        int result = 0;                // 当前窗口的长度
        int bestResult = 0;            // 最长无重复字符的子串长度

        while (right < s.length()) {
            char rChar = s[right];     // 右指针对应的字符
            if (map.find(rChar) != map.end()) {
                // 如果字符已经存在，则可能需要移动左指针
                left = max(left, map[rChar] + 1);
            }
            map[rChar] = right;        // 更新或添加字符的最新索引
            result = right - left + 1; // 更新当前窗口的长度
            bestResult = max(bestResult, result); // 更新最长子串的长度
            right++;                   // 移动右指针
        }

        return bestResult;
    }
};

使用数组优化哈希表

int lengthOfLongestSubstring(string s) {
    vector<int> index(256, -1);  // ASCII 字符集，所有元素初始化为 -1
    int left = 0, right = 0;
    int bestResult = 0;

    while (right < s.length()) {
        char rChar = s[right];
        // 如果当前字符已出现过且索引大于等于左指针，则更新左指针
        if (index[rChar] != -1 && index[rChar] >= left) 
            left = index[rChar] + 1;
        // 更新当前字符的索引
        index[rChar] = right;
        // 计算当前无重复字符子串的长度，并更新最长长度
        bestResult = max(bestResult, right - left + 1);
        // 移动右指针
        right++;
    }

    return bestResult;
}

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

拿到本题很直观的感觉，我们需要一个容器装p，记录他出现的字母和次数，然后需要一个容器装我们滑动窗口中的字符，然后这两个容器如果匹配上了，那肯定就是异构词了。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.size() < p.size()) return result;

        unordered_map<char, int> pCount, sCount;

        //初始化p的字符频率表
        for (char c : p) {
            pCount[c]++;
        }

        int left = 0, right = 0;
        int required = p.size();
        while (right < s.size()) {
            //加入当前右指针
            char rChar = s[right];
            sCount[rChar]++;

            //当窗口大小匹配P长度时进行比较
            if (right - left + 1 == required) {
                if (sCount == pCount) { //存结果
                    result.push_back(left);
                }
                //否则窗口左端向右移动，缩小窗口
                sCount[s[left]]--;
                if (sCount[s[left]] == 0) {
                    sCount.erase(s[left]);
                }
                left++;
            }
            right++;
        }
        return result;
    }
};

数组优化

我们使用固定大小的数组代替哈希表
减少不必要的比较
- 我们在之前的实现，每次窗口大小达到p长度时，我们都会比较两个哈希表，我们可以只在字符频率匹配时才进行这样的比较，即当插入或删除操作可能改变频率表到匹配状态时才检查。
滑动窗口计数
- 维护一个计数器来跟踪已匹配的字符种类数量。例如，当某个字符的期望频率与窗口中的频率相匹配时，增加计数器。如果所有字符都匹配，计数器将等于不同字符的总数。这样可以在不比较整个哈希表（指数组）的情况下，通过检查计数器来判断当前窗口是否为有效的异位词。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.size() < p.size()) return result;

        vector<int> pCount(256, 0), sCount(256, 0);
        for (char c : p) {
            pCount[c]++;
        }

        int left = 0, right = 0, count = 0;
        int pLength = p.size();

        while (right < s.size()) {
            // 增加右指针字符
            if (pCount[s[right]] > 0 && ++sCount[s[right]] <= pCount[s[right]]) {
                count++;
            }
            // 当窗口大小正确，并且计数匹配
            if (right - left + 1 == pLength) {
                if (count == pLength) {
                    result.push_back(left);
                }
                // 减少左指针字符
                if (pCount[s[left]] > 0 && sCount[s[left]]-- <= pCount[s[left]]) {
                    count--;
                }
                left++;
            }
            right++;
        }
        return result;
    }
};

76. 最小覆盖子串

和上一题几乎一样

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty() || s.size() < t.size()) return "";

        // 字符计数数组
        unordered_map<char, int> need, have;
        for (char c : t) {
            need[c]++;
        }

        // required 表示需要涵盖的字符种类数
        int required = need.size();
        int left = 0, right = 0, formed = 0;
        int minLen = INT_MAX, minStart = 0; // 用于记录最小子串的起始位置和长度

        while (right < s.length()) {
            char c = s[right];
            have[c]++;

            // 如果当前字符的数量符合需求的数量，增加formed
            if (need.count(c) && have[c] == need[c]) {
                formed++;
            }

            // 尝试缩小窗口，直到窗口不再满足条件
            while (left <= right && formed == required) {
                char temp = s[left];
                // 更新最小窗口
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minStart = left;
                }
                // 移动左指针，更新have数组和formed计数
                have[temp]--;
                if (need.count(temp) && have[temp] < need[temp]) {
                    formed--;
                }
                left++;
            }

            // 移动右指针
            right++;
        }

        return minLen == INT_MAX ? "" : s.substr(minStart, minLen);
    }
};