【看海的算法日记✨优选篇✨】第二回：流动之窗，探索算法的优雅之道

🌈 个人主页：谁在夜里看海.

🔥 个人专栏：《C++系列》《Linux系列》《算法系列》

⛰️ 道阻且长，行则将至

一、算法思想

双指针

滑动窗口

二、具体运用

1.⻓度最⼩的⼦数组

算法思路

算法流程

代码

2.最⼤连续1的个数III

算法思路

算法流程

代码

3.⽔果成篮

算法思路

算法流程

代码

4.串联所有单词的⼦串

算法思路

算法流程

代码

三、总结

一、算法思想

上一章我们介绍了双指针的算法思想，其核心原理是利用两个指针在数组中移动，以高效解决一个涉及有序序列、子区间的问题。我们主要介绍的是用于解决在有序区间中判断元素对的场景，即判断两个指针指向的元素，并利用序列的单调性完成指针的移动。

我们今天要讲的滑动窗口本质是双指针算法的特化，它与上一章所讲的双指针有所区别：

特性	双指针	滑动窗口
移动方向	两个指针可以同向移动或对向移动	只能同向移动，窗口随之调整
窗口特性	不一定维护特定的窗口，只关注指针的状态	维护一个动态窗口，用于表示当前连续区间
使用场景	常用于查找元素对，判断满足条件	常用于处理连续子数组或子字符串的问题
条件变化	两个指针的关系由问题决定，没有固定结构	窗口大小动态变化，与目标条件有关

双指针

滑动窗口

在每次调整窗口后，判断窗口是否满足条件，如果能满足，更新结果以记录最优解。

只看算法原理可能又有些抽象，下面看看具体的使用场景：

二、具体运用

1.⻓度最⼩的⼦数组

难度等级：⭐⭐⭐⭐

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题目描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的

子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

算法思路

暴力枚举：

这道题目的暴力枚举思路是，把每一个区间都枚举出来，筛选出元素总和满足条件的，然后再进一步筛选区间长度最短的，就是最终结果。枚举全部区间我们首先想到的是用两层for循环，但那样时间复杂度太高了，所以我们选择用双指针进行优化：定义left、right指针，用指针的移动完成对数组的遍历。

遍历的过程为：固定left指针为区间的起始位置，right向后一次遍历，枚举出当前起始位置下的所有区间，这里我们要想一个问题，right指针需要将所有元素都遍历一遍吗？并不需要，我们可以在right遍历的过程中，实时地记录当前区间元素和，当元素和>target（满足条件）时，right就不需要要继续遍历了，因为题目要求的是区间长度最小的，再遍历下去长度只会增大。于是我们的滑动窗口思想就产生了：

滑动窗口：

延续上面的思路，固定left作为区间起始位置，right在遍历的过程中找到当前起始位置下满足题目条件（区间元素和>target）的情况时停止遍历，那么接下来应该怎么做呢？移动left指针，修改区间的起始位置，right指针需要从起始位置开始重新遍历吗？并不需要，移动left指针之前我们找的的区间是刚好满足题目条件的情况，此时移动left指针，区间元素减少，那么这一段区间肯定都是不满足条件的，所以right指针不需要回到起始位置，从当前位置继续向后遍历即可。

算法流程

①：定义left、right指针，初始都指向数组首元素；

②：固定left指针，作为区间起始位置，right从起始位置开始向后遍历，遍历的过程中记录区间内元素总和，当元素总和>target时，停止遍历，记录当前区间长度；

③：移动left指针，改变区间起始位置，right不需要回到起始位置，直接从当前位置向后遍历，后续操作与步骤②一样；

④：最后找到满足条件的最短区间情况。

代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0,right = 0,sum = nums[right],len = INT_MAX;
        while(right<nums.size())
        {
            if(sum<target)
            {
                ++right;
                if(right<nums.size()) sum+=nums[right];
            }
            else
            {
                if(left == right) return 1;
                len = min(len,right-left+1);
                sum-=nums[left];
                ++left;
            }
        }
        return len == INT_MAX ? 0:len;
    }
};

可以看到我们的时间复杂度是非常优秀的

2.最⼤连续1的个数III

难度等级：⭐⭐⭐⭐

题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

题目描述：

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

算法思路

这道题也是让我们找一个满足条件的区间，与上一题类似，有了上一题的铺垫，这道题我们直接从滑动窗口的思想入手：

首先我们还是确定区间起始位置，下一步需要考虑是right遍历的终止情况，即right何时停止遍历。题目让我们找的是连续1的最长区间，并且告诉我们，区间内允许出现k个0元素，所以我们right终止遍历的情况就是：遇到0元素且翻转次数k用完，此时就是当前起始位置下的最长区间。

后面的操作就是移动left指针，修改区间起始位置，那么left是移动一次吗？并不是，如果只移动一次，并不能支持right向后遍历，因为k没有增加，而right当前指向的是0元素，所以left需要一直移动直到将一个0元素“挤出”区间，此时k才会增加，right才能继续遍历。

算法流程

①：初始化left、right指针，指向数组首元素；

②：固定left，作为区间起始位置，right向后遍历，并实时记录当前k的使用情况，遇到0时k--，当k减到0时并且right来到下一个0元素之前，停止遍历，记录当前区间长度；

③：移动left，修改区间起始位置，left需要排出一个0元素方可停止移动，然后right继续遍历；

④：最后找到满足条件的最长区间。

代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0,right = 0,flag = k,num = 0,ret = 0;
        for(right;right<nums.size();++right)
        {
            // 为1,继续遍历
            if(nums[right])
            {
                ++num;
                ret = max(num,ret);
            }
            // 为0,减小计数
            else
            {
                --flag;
                if(flag>=0)
                {
                    ++num;
                    ret = ret>num?ret:num;
                    continue;
                }

                // 计数用完，移动left直到跳过一个0，返还一个计数
                while(nums[left])
                {
                    ++left;--num;
                }
                ++left;++flag;
            }
        }
        return ret;
    }
};

3.⽔果成篮

难度等级：⭐⭐⭐⭐

题目链接：904. 水果成篮 - 力扣（LeetCode）

题目描述：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

算法思路

题目描述很长，简单概括一下就是：在数组中找到一个连续区间，区间内只能包含两种元素，筛选出满足条件的最长区间。

既然是寻找连续区间，那还是用滑动窗口进行解决：

首先依旧是固定区间起始位置，用right指针向后遍历，遍历的终止情况是，区间内已经包含两种元素，并且right位置的下一个元素是第三种元素，我们可以用一个type变量监控当前区间的元素种类

然后是left的移动，修改区间起始位置，同样地left的移动需要将一种元素全部“排除”区间，使type+1，right方可继续遍历。

算法流程

①：初始化left、right，指向数组首元素；

②：固定left，作为区间起始位置，right向后遍历，遇到一种新元素，type--，直到type减到0并且right来到下一种元素前一个位置；

③：移动left，修改区间起始位置，left的移动需要排出全部的一种元素，right才能继续遍历；

④：最终筛选出满足条件的最长区间。

代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0,right=0,hash[100000]={0},type=0,ret=0;
        while(right<fruits.size())
        {
            if(hash[fruits[right]]==0) ++type;
            ++hash[fruits[right]];++right;
            if(type == 3)
            {
                ret=max(ret,right-left-1);
                // 移动窗口 直到type-1
                while(type == 3)
                {
                    --hash[fruits[left]];
                    if(!hash[fruits[left]]) --type;
                    ++left;
                }
            }
        }
        if(type==1) return fruits.size();
        if(type==2) return max(ret,right-left);
        return ret;
    }
};

4.串联所有单词的⼦串

难度等级：⭐⭐⭐⭐⭐

题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）

题目描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"，和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

算法思路

题目的要求是让我们在字符串中寻找一个连续区间，区间内包含数组words中的全部字符串，找到满足条件的所有区间。

我们定义一个哈希表，用来存储数组words中的全部字符串，并定义一个count，用于记录区间内还需要包含元素的个数。right向后遍历一个字符串时，对该字符串进行判断，如果存在于哈希表中，--count。当前遍历的字符串不存在哈希表中时，需要终止遍历，当count减到0时，记录当前区间起始位置；

对于left的移动，我们需要分为两种情况讨论：

①：left==right，说明区间内部不包含元素，需要同时移动left与right

②：left<right，由于right遍历时，只有当前字符串存在于哈希表中，才会继续遍历，这样就保证了区间内元素都是符合条件的，所以此时left只需要向后移动排除一个字符串，count++，支持right继续向后遍历。

注意：

上述思路是存在缺陷的，因为left和right都是以字符串的长度向后遍历的，并不是依次遍历，所以这个过程会遗漏很多情况，我们需要考虑到这些情况，解决办法就是：对区间起始位置加上一个偏移量，如果字符串长度为3，那偏移量范围就是0~2

算法流程

①：初始化left、right，初始值为0+偏移量；

②：固定left，作为区间首元素，left以字符串长度向后遍历，判断当前字符串是否存在哈希表中，如果存在，count--；如果不存在，移动left，修改区间。当count减到0时，记录当前区间起始位置，并移动left，修改区间；

③：移动left分为两种情况：

a.left==right，说明区间为空，left和right同时向后移动；

b.left<right，说明区间存在元素，left向后移动一个字符串，count--，当前位置作为区间起始位置，right继续向后变量。

④：找到满足条件的所有区间。

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash;
        for(auto it:words) ++hash[it];
        int len = words[0].size();
        vector<int> ret;
        for(int i = 0;i<len;++i)
        {
            unordered_map<string,int> target = hash;
            int left = i,right = i;
            int count = words.size();
            while(right<s.size())
            {
                string cur = s.substr(right,len);
                if(target.count(cur) && target[cur]>0)
                {
                    --target[cur]; --count;
                    right += len;
                }
                else
                {
                    if(left != right)
                    {
                        string del = s.substr(left,len);
                        ++target[del]; ++count;
                        left += len;
                    }
                    else
                    {
                        right += len;
                        left += len;
                    }
                }
                if(count == 0)
                {
                    ret.push_back(left);
                    string del = s.substr(left,len);
                    ++target[del]; ++count;
                    left += len;
                }
            }
        }
        return ret;
    }
};