【C++例题 / 训练】滑动窗口（总结&&例题）

IsLand1314

发布于 2024-10-15 20:32:35

18300

代码可运行

文章被收录于专栏：学习之路学习之路

运行总次数：0

代码可运行

本篇主要总结关于滑动窗口的相关做题技巧与注意事项，滑动窗口也用到了双指针的内容，可以参考这篇文章【算法/学习】双指针-CSDN博客，本篇主要用于在了解滑动窗口的构造后，快速掌握滑动窗口的做题技巧与做题模板，便于以后复习参阅

定义变量：确定需要维护的变量：数之和，最大最小长度，哈希表等
滑动窗口：确定滑动窗口的左右边界，开始滑动窗口
合法更新：在滑动窗口有效的情况下，合法的更新需要维护的变量
非法更新（二次更新）：在滑动窗口无效或者即将无效的情况下，更新维护的变量，并且收缩滑动窗口的左边界

非法更新的两种情况：
    滑动窗口的长度是固定的！！！ 使用 if条件来更新
    滑动窗口的长度是可变的！！！ 使用 while / for 条件来更新
返回与得到答案

经典例题如下

定长滑动窗口

1. 字符串的排列

思路： 由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。 根据这一性质，记 s1 的长度为 n，我们可以遍历 s2 中的每个长度为 n 的子串，判断子串和 s1 中每个字符的个数是否相等，若相等则说明该子串是 s1 的一个排列。使用两个数组 cnt1 和 cnt2，cnt1 统计 s1 中各个字符的个数，cnt2 统计当前遍历的子串中各个字符的个数。由于需要遍历的子串长度均为 n，我们可以使用一个固定长度为 n 的滑动窗口来维护 cnt2：滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。然后，判断 cnt1 是否与 cnt2 相等，若相等则意味着 s1 的排列之一是 s2 的子串。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) return false;
        vector<int> cnt1(26), cnt2(26); //哈希映射
        for (int i = 0; i < n; i++) {
            ++cnt1[s1[i] - 'a'];
            ++cnt2[s2[i] - 'a'];
        }

        if (cnt1 == cnt2) return true; //当两个数组内存储数据相同时则返回true
        for (int i = n; i < m; i++)
        {
            ++cnt2[s2[i] - 'a']; //后面的进窗口
            --cnt2[s2[i - n] - 'a']; //前面的出窗口
            if (cnt1 == cnt2) return true;
        }
        return false;
    }
};

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

思路： 该题与上题的字符串排列很像，由于我们需要找在字符串 s 寻找字符串 p 的异位词，故其异位词长度肯定与 p 长度相同，因此我们可以在 s 中构造一个定长的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。 注：

使用数组来存储字符串 p 和滑动窗口中每种字母的数量
当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。

class Solution {
public:
    vector<int> ans;
    vector<int> findAnagrams(string s, string p) {
        int n = s.length(), m = p.length();
        if (n < m) return ans;
        vector<int> nums1(26), nums2(26);
        for (int i = 0; i < m; i++){
            ++nums1[s[i] - 'a'];
            ++nums2[p[i] - 'a'];
        }

        if (nums1 == nums2) ans.push_back(0);

        for (int i = 0; i < n - m; i++) // 从 0 开始
        {
            --nums1[s[i] - 'a']; //前面出窗口
            ++nums1[s[i + m] - 'a'];  //后面进窗口
            if (nums1 == nums2) 
                ans.push_back(i + 1);
        }
        return ans;
    }
};

方法二：

解析如下：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        int hash1[26] = { 0 }; //统计字符串 p 中每个字符出现次数
        for (auto e : p) hash1[e - 'a']++;
        int hash2[26] = { 0 }; //统计窗口中每个字符出现次数
        int m = p.size();
        for (int l = 0, cnt = 0, r = 0; r < s.size(); r++) // cnt 表示窗口内有效字符数目
        {
            char in = s[r];
            //进窗口 + 维护 cnt
            hash2[in - 'a']++;
            if (hash2[in - 'a'] <= hash1[in - 'a']) cnt++; 
             // 判断
            if (r - l + 1 > m)
            {
                char out = s[l++];
                //出窗口 + 维护cnt
                if (hash2[out - 'a'] <= hash1[out - 'a']) cnt--; 
                --hash2[out - 'a'];
            }
            // 更新结果
            if (cnt == m) ans.push_back(l);
        }
        return ans;
    }
};

可变滑动窗口

1. 长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX; 
        // 1.  l、r左右指针，sum计算窗口内总和
        int l = 0, r = 0, sum = 0; 
        while (r < nums.size()) {
            // 2. 合法更新，窗口滑动一下，把这个数字想加，计算之和
            sum += nums[r];
            // 3. //4. 非法更新（二次更新）：当sum满足条件时，试探是否有更好的办法可以实现，即缩小窗口，有没有长度更小的子数组满足>=target
            while (sum >= target) {
                ans = min(ans, r - l + 1);
                sum -= nums[l++];
            }
            r++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

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

思路： 滑动窗口+ 哈希即可

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //1. 确定维护变量：存储字符个数的哈希表
        unordered_set<char> hash;
        int maxStr = 0;
        //2. 定义滑动窗口的边界：开始滑动窗口
        int l = 0, r = 0;
        while (r < s.size())
        {
            //3. 查找是否出现重复字符
            while (hash.find(s[r]) != hash.end()) //从前往后清除，直到清除完重复字符
            {
                hash.erase(s[l]);
                l++;
            }
            // 4. 更新
            maxStr = max(maxStr, r - l + 1);
            hash.insert(s[r++]);
        };
        //5. 返回结果
        return maxStr;
    }
};

3. 最短超串

思路：

先用哈希数组 hash1 记录短数组内数据的映射情况，并且记录短数组内数字的种类。
用cnt来维护窗口内符合短数组的有效数字，minLen记录最短长度，begin记录头节点
然后双指针进行滑动窗口即可

注：哈希数组需要开的大一些，否则会出现越界情况

class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small)
    {
        int hash1[10000005] = { 0 }, kinds = 0;  //统计短数组中每一个数字的频次
        for (auto e : small)
        {
            if (hash1[e]++ == 0) kinds++; 
        }

        int hash2[10000005] = { 0 }; //统计窗口内每个数字频次
        int minLen = INT_MAX,begin = -1;
        for (int l = 0, r = 0, cnt = 0; r < big.size(); r++)
        {
            //进窗口+ 维护 cnt
            int in = big[r];
            hash2[in]++;
            if (hash2[in] == hash1[in]) cnt++;
            //判断
            while (cnt == kinds)
            {
                if (r - l + 1 < minLen) //更新结果
                {
                    minLen = r - l + 1;
                    begin = l;
                }
                //出窗口
                int out = big[l++];
                if (hash2[out] == hash1[out]) cnt--;
                hash2[out]--;
            }
        }
        if (begin == -1) return {};
        else return { begin, begin + minLen - 1};
    }
};

4. 最小覆盖子串

思路： 该题与上题思路相同。

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 }; //统计字符串 t 中每一个字符的频次
        int kinds = 0; //统计有效字符种类
        for (auto e : t)
        {
            if (hash1[e]++ == 0) kinds++;
        }

        int hash2[128] = { 0 }; //统计窗口内每个字符频次
        int minLen = INT_MAX, begin = -1;

        for (int l = 0, r = 0, cnt = 0; r < s.size(); r++)
        {
            // 进窗口 + 维护 cnt
            char in = s[r];
            hash2[in]++;
            if (hash2[in] == hash1[in]) cnt++;
            //判断
            while (cnt == kinds)
            {
                if (r - l + 1 < minLen) //更新结果
                {
                    minLen = r - l + 1;
                    begin = l;
                }
                // 出窗口
                char out = s[l++];
                if (hash2[out] == hash1[out]) cnt--;
                hash2[out]--;
            }
        }
        return begin == -1 ? "" : s.substr(begin, minLen);
    }
};

5. 将 x 减到 0 的最小操作数

思路： 正难则反：转化为找出最长子数组的长度，所有元素的和正好等于 sum - x.

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int target = sum - x; //找最长的子数组和为target
        if (target < 0) return -1;

        int ret = -1, tmp = 0; 
        for (int l = 0, r = 0; r < nums.size(); r++)
        {
            tmp += nums[r]; //进窗口
            while (tmp > target) //判断
                tmp -= nums[l++]; //出窗口
            if (tmp == target) //更新结果
                ret = max(ret, r - l + 1);
        }
        return ret == -1 ? -1 : nums.size() - ret;
    }
};

6. 水果成篮

思路： 该题本质就是求只含有两种不同字符的最长子串 使用滑动窗口解决本题，left 和 right 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数以及出现的次数。我们每次将 right 移动一个位置，并将 fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left，并将 fruits[left] 从哈希表中移除，直到哈希表满足要求为止。注：需要注意的是，将 fruits[left] 从哈希表中移除后，如果 fruits[left] 在哈希表中的出现次数减少为 0，需要将对应的键值对从哈希表中移除。

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        unordered_map<int, int> cnt;
        int l = 0, r = 0, ans = 0;
        while (r < n)
        {
            ++cnt[fruits[r]];
            while (cnt.size() > 2)  //窗口种类 > 2时，则出窗口直到种类为1为止
            {
                // 出窗口
                cnt[fruits[l]]--;
                if (cnt[fruits[l]] == 0) cnt.erase(fruits[l]); //当窗口内该种类数目为0，则删除该种类
                l++;
            }
            ans = max(ans, r - l + 1);
            r++;
        }
        return ans;
    }
};

7. 串联所有单词的子串

思路： 该题的思路和找到字符串中所有字母异位词很像。主要解决方法和那题的方法二类似。定义两个哈希数组 hash1，hash2。 hash1 记录words的字符串，hash2记录窗口内的字符串，cnt用来记录有效字符串。 优化：hash.count() 先来判断该字符串是否存在

class Solution {
public:
    vector<int> ans;
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash1;
        for (auto e : words) hash1[e]++;
        
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) //执行len次，相当于对长为n的字符串，依次往后划分
        {
            unordered_map<string, int>hash2; //维护窗口内的频次
            // 滑动窗口
            for (int l = i, r = i, cnt = 0; r + len <= s.size(); r += len)
            {
                //进窗口 + 维护cnt
                string in = s.substr(r, len);
                hash2[in]++;
                // 优化：hash.count() 先来判断该字符串是否存在
                if (hash1.count(in) && hash2[in] <= hash1[in]) cnt++; // 说明是有效字符串
                //判断
                if (r - l + 1 > len * m)
                {
                    // 出窗口 + 维护 cnt
                    string out = s.substr(l, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out]) cnt--;
                    hash2[out]--;
                    l += len;
                }
                // 更新结果
                if (cnt == m)  ans.push_back(l);
            }
        }
        return ans;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent.com 删除

c++