算法练习——滑动窗口网站首页 其他

算法练习——滑动窗口

梦想成为小钩晴 2026-03-09 12:01:04

简介算法练习——滑动窗口

前言：滑动窗口的难点不在于怎么编写代码，而在于如何想到这题是用滑动窗口的算法去解决。其次滑动窗口存在单调性。

一：长度最小的子数组

题目要求：

解题思路：

对于第一道滑动窗口算法题而言，去熟悉这一过程，想想这个过程是怎么得到最终答案的，不用考虑为什么这题要使用滑动窗口。

题目要求是：找几个相邻的数据，他们的和大于等于target，要你求出相邻数据长度最小的值。

如果通过暴力算法，能解决，但是肯定会超时。暴力算法的缺陷时，重复的数据会多次计算，

问：那么如何优化算法，才能够避免重复计算呢？

答：我也答不出来，但是可以通过下图来尝试解释优化的过程。

我们的第一目标是要使得连续的几个数据相加的和 ≥ target，

那么我们定义一个 sum，

让 sum += arr[right++]，直至满足条件时（示例1），如下图：

此时已经满足了题给条件。

问：接下来该怎么做呢？

答：定义一个 len 去记录实时的数据范围的长度。

问：定义好了然后呢？让right++吗？

答：显然right此时不应该++，因为再往右++，始终满足范围内数据大于 target ，且 len 不是我们所要的最小值。因此此时应该变动 left 了。

问：left 仅仅只是++吗？

答：显然也不是，如果仅仅是对left++ 的话，sum的数据仍然≥target，所以再left++之前，需要先更新sum的数据，即 sum-=arr[left]，且应该是循环这个过程，直至sum不满足条件，之后right再次++，直至循环结束。

在这一过程，可以看到，当right为2时，我们让left++，这样就少考虑了right 右边 4 3 的情况，在后续遍历中，同样会避免对重复或者是无用数据的计算次数，因此在这一过程中，优化了算法。

实现代码：

int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int len = INT_MAX;
        int sum = 0;

        for(int left = 0,right = 0;right < n;)
        {
            sum+=nums[right];
            while(sum >= target)
            {
                len = min(len,right - left + 1);//满足target条件时，更新len 再做变动
                sum -= nums[left];
                left++;
            }
            right++;
        }
        if(len == INT_MAX)
        {
            return 0;
        }
        else
        {
            return len;
        }
    }

二：无重复字符的最长子串

题目要求：

解题思路：

上一题是借助 sum 是否满足target 来判断是否要出窗口

此题需要用到hash表（博主此时还没学过哈希，将哈希的思想理解成计数排序的思想）的思路去判断是否需要出窗口

借助下图来解释思路（示例1）：

定义一个数组 int hash[128] = {0}；先前我们学过计数排序的思想，即对应下标位置处的数据++；

hash[arr[right++]]；right在向右遍历的过程中，对应的下标会不断++

注：arr[right]是字符数据，数组会将字符数据转换成对应的ASCII码值，即对应下标的数据会+1。

当 right 来到该位置处时，此时hash数组中，对应的下标位置处的数据已然为2，此时说明字串已经重复，此时需将a的ASCii码对应下标位置的数据--，再令left++

实现代码：

    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};
        int n = s.size();
        int len = 0;
        for(int left = 0,right = 0;right <n;)
        {
            hash[s[right]]++;
            while(hash[s[right]] > 1)
            {
                hash[s[left]]--;
                left++;
            }
            len = max(len,right - left+1);
            right++;
        }
    return len;
    }

三：将x减到0的最小操作数

题目要求：

解题思路：

这道题的关键在于逆向思维，读了这么多年书了，逆向思维大家应该都不陌生了。

如果我们直接做这道题，会发现既要在左边遍历，又要在右边遍历，还要对比数据大小，那么这道题的难度就会变得很夸张。

不妨多思考一下，换一个角度考虑。例如不去找两头的数据，而是中间的呢？不难发现，中间的数据是连在一起的，中间数据的值 = 数据总和 - x

那么这道题就被转换成了：在数组中找一串连续的数据，满足以下两个要求

①：连续数据的和为：数据总和 - x

②：连续数据的长度最长

滑动窗口算法：

该算法有固定的部分：将数据入窗口，将数据出窗口

变化的部分是：出窗口的条件，以及何时更新我们想要的结果，和部分细节上的问题。

以下图为例：目标找满足和为20的数

定义 sum = 0；

开始时，持续入窗口 sum+= nums[right]; right++;

当指针来到下图位置时，sum > 20

此时需要出窗口，并更新窗口内数据大小，直至他不满足 > 20

当left指针来到下图位置时，恰巧找了我们需要的目标值

此时更新结果值，并继续循环直至结束。

代码实现：

 int minOperations(vector<int>& nums, int x) {
        int sum_num = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum_num += nums[i];
        }
        int target = sum_num - x;
        if(target < 0)
        {
            return -1;
        }
        int sum = 0;
        int len = -1;
        for(int left = 0, right = 0; right < nums.size();right++)
        {
            sum += nums[right];
            while(sum > target)
            {
                sum -= nums[left];
                left++;
            }
            if(sum == target)
            {
                len = max(len , right - left + 1);
            }
        }
        if(len == -1)
        {
            return len;
        }
        else
        {
            return nums.size() - len;
        }
       
    }

注：上述代码有个注意点：target 可能为负，此时需要直接返回 -1

四：水果成篮

题目要求：

解题思路：

分析：简化一下题目，在一个整型数组fruit中，找到只包含两种数字的最大子串。

思路：借助哈希表——unordered_map<int,int> hash;来记录每种数字，以及其出现的次数

以示例4为例，初始情况如下图

进窗口：

hash[f[right]]++; 记录当前水果，以及其出现次数，当right如下图位置时，需要出窗口

出窗口：

当 hash.size() > 2 时，说明此时窗口内数字种类已超过2，不满足题目要求。。此时left需要++，但是left++前，需更新当前窗口信息，hash[f[left]]--;

当hash[f[left] == 0];时，此时需将该数字从hash表中删除

需要循环出窗口，直至满足数字个数要求，如下图所示：

更新结果：

每次进窗口时，更新Max值

实现代码：

class Solution {
public:
    int totalFruit(vector<int>& f) {
        unordered_map<int,int> hash;
        int Max = 0;
        for(int left = 0,right = 0; right < f.size(); right++) {
            hash[f[right]]++;
            while(hash.size() > 2) {
                hash[f[left]]--;
                if(hash[f[left]] == 0) {
                    hash.erase(f[left]);
                }
                left++;
            }
            Max = max(Max,right-left+1);
        }
        return Max;
    }
};

五：找到字符串中所有字母异位词

题目要求：

解题思路：

法一（以示例1为例）：如下图定义两个变量

定义一个哈希表——int hash[26] = {0}; 来记录每个字母出现的个数

进窗口：

hash[s[right] - 'a']++;直至如图所示

出窗口：

当right - left + 1 > 子串长度(p.size())时，left需++，在left++前，需要先更新当前窗口，即hash[s[left] - 'a']--;

注：本题中，窗口大小是固定的，因此只需要出一次窗口即可

更新结果：

当 right - left + 1 = 子串长度，写一个判断函数，将hash与p传入，判断是否为异位词，是则更新结果

法二（以示例1为例）：区别于法一的是，通过维护另一个count变量，来更新结果。

初始变量如下图所示：

解释：

hash1[26]用于记录子串p中，所有字母出现的个数

hash2[26]用于记录字符串s中，left~right所有字母出现的个数

进窗口：

hash2[s[right] - 'a']++;

判断 if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) 若满足条件，说明此时hash2中进入了一个有效的字母，所以count++

解释：当前right处的字母为c，hash2[s[right] - 'a']++;将字母c插入到了hash2中，因为hash1中也包含了字母c，且只有一个，那么说明hash2中插入的字母为有效字母，count需要++，👉：假设插入的第二个字母也是c，但hash1中只有一个字母c，那么此时hash2中字母c的个数大于hash1中字母c的个数，说明第二次插入的c不是有效字母，因此count不++；

👉：假设插入的第二个字母是e，但是hash1中没有字母e，说明插入的也不是有效字母，因此count不++

循环进窗口直至如图所示：

出窗口：

当right - left + 1 > 子串长度时，需要出窗口，如图所示

hash2[s[left] - 'a']--;

判断if(hash2[s[left] - 'a'] < hash1[s[left] - 'a']) count--;

解释：

需要判断当前出hash2的字母是否为有效字母，若为有效字母，则count--;如图所示

可以看到此时count == 2，无法满足更新结果的条件

更新结果：

当 count == 子串长度时，说明此时hash2和hash1互为异位词。left为答案之一。如图所示

实现代码：

法二：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0}, hash2[26] = {0};
        for(auto& w : p) {
            hash1[w - 'a']++;
        }
        vector<int> ret;
        for(int left = 0, right = 0, count = 0, len = p.size(); right < s.size(); right++) {
            hash2[s[right] - 'a']++;
            if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) {
                count++;
            }
            if(right - left + 1 > len) {
                hash2[s[left] - 'a']--;
                if(hash2[s[left] - 'a'] < hash1[s[left] - 'a']) {
                    count--;
                }
                left++;
            }
            if(right - left + 1 == len && count == len) {
                ret.push_back(left);      
            }
        }
        return ret;
    }
};

六：串联所有单词的子串

题目要求：

解题思路：

明确变量：

int len = words[0].size(); → words中，每一个子串的长度

int total = words.size(); → words的个数：

以示例1为例：

思考一个问题：left和right该怎么更新？每次+1吗？

答：显然不可以，如果一个一个更新，那么每次只能统计一个字母，当满足right - left + 1 = len 时，在记录当前字符串，这显然太复杂了！！！！所以left和right每次应该+=len

定义一个变量 string in = s.substr(right,len);来构建当前s中的子串，进而做进一步的讨论。

思考另一个问题：这么做带来的问题就是，以第二个或者第三个为起始的子串没法遍历。

答：为此我们需要在外部再套一层循环，循环len次。如图所示，一次讨论一种情况

思路：明确上述后，本题的思路就和第五题的法二没有太大区别了。

明确变量：

unordered_map<string,int> hash1; 用于记录p中所有字符串出现的个数

unordered_map<string,int> hash2; 用于记录当前left~right+len所构成的字符串出现的次数

起始如图所示：

进窗口：

string in = s.substr(right,len);

hash2[in]++;

判断 if(hash1.count(in) && hash2[in] <= hash1[in]) count++；若当前进窗口的字符为有效字符，则count++；

出窗口：

当right - left + 1 > total * len 时，需要出窗口，因为窗口大小固定，所以只需要出一次。

string out = s.substr(left,len);

hash2[out]--;

判断 if(hash1.count(out) && hash2[out] < hash1[out]) 若当前出窗口的字符为有效字符，则count--；

left += len;

可以看到此时窗口大小满足题目答案要求，但是count = 1，说明有效字符串个数不足，因此此时left处不满足题目要求。

更新结果：

如果count == total，则left位置处为答案之一。

实现代码：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash1;
        for(auto str : words) {
            hash1[str]++;
        }
        vector<int> ret;
        int len = words[0].size(), total = words.size();
        for(int i = 0; i < len; i++) {
            unordered_map<string,int> hash2;
            for(int left = i, right = i,count = 0; right + len <= s.size(); right += len) {
                string in = s.substr(right,len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) {
                    count++;
                }
                if(right - left + 1 > total * len) {
                    string out = s.substr(left,len);
                    hash2[out]--;
                    if(hash1.count(out) && hash2[out] < hash1[out]) {
                    count--;
                    }
                    left += len;
                }
                if(count == total) {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};

七：最小覆盖子串

题目要求：

解题思路：

思路：

明确变量：

int Begin = -1; 用于记录最小子串的起始位置

int Min = INT_MAX; 用于记录最小子串的长度

int hash1[128] = {0}; 用于记录子串t中所有字母出现的个数

int hash2[128] = {0}; 用于记录字符串s中 left~right 所有字母出现的个数

int count = 0; 用于记录hash2中，有效字母的个数

初始如下图所示：

进窗口：

hash2[s[right]]++;

判断if(hash2[s[right]] <= hash1[s[right]])，若满足条件，说明此时进入hash2的为一个有效字母，则count++；

出窗口：

当count == t.size()时，说明此时hash2中已经包含了hash1中所有的字母，如图所示：

1.在窗口中更新结果

判断if(right - left + 1 < Min)，若满足条件，则Begin = left，Min = right - left + 1；

2.再出窗口

hash2[s[left]]--；

3.更新窗口信息

if(hash2[s[left]] < hash1[s[left]]) 若条件成立，则说明出窗口的字母为有效字母，则count--；

4.left++；

注：此处需要循环出窗口

解释：第一次满足条件时，因为hash2中出去的第一个字母就是有效字母，为此循环直接结束，当第二次满足条件时，此时如图所示：

hash2中出去的第一个字母不是有效字母，count仍然等于3，

若并非循环出窗口，那么在right到字符串末尾时，都无法得到我们想要的答案，

若为循环出窗口，可以看到，hash2中会将无效字母循环去除，在这个过程中Min的值会逐渐减小，直至有效字母的个数变为2，此时得到一个临时的Min和Begin。

当第三次满足条件时，如图所示：

循环出窗口至如图所示：

因为是先更新的Min和Begin，left在++，所以此时Min和Begin就是我们想要的答案。

实现代码：

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0};
        int hash2[128] = {0};
        for(auto& w : t) {
            hash1[w]++;
        }
        int Min = INT_MAX;
        int Begin = -1;
        for(int right = 0, left = 0, count = 0; right < s.size(); right++) {
            hash2[s[right]]++;
            if(hash2[s[right]] <= hash1[s[right]]) {
                count++;
            }
            while(count == t.size()) {
                if(right - left + 1 < Min) {
                    Min = right - left + 1;
                    Begin = left;
                }
                hash2[s[left]]--;
                if(hash2[s[left]] < hash1[s[left]]) {
                    count--;
                }
                left++;
            }
        }
        if(Begin == -1) {
            return "";
        }
        else {
            return s.substr(Begin,Min); 
        }
    }
};

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。