解锁高效算法思维：滑动窗口法，让你轻松搞定复杂题！（1）

用户11295429

发布于 2024-11-19 11:03:48

8400

代码可运行

文章被收录于专栏：王的博客专栏王的博客专栏

运行总次数：0

代码可运行

解锁高效算法思维：滑动窗口法，让你轻松搞定复杂题！（1）

前言：

小编在前几日做了关于双指针的题目，算法的类型是有很多种的，今天小编开一个新的类型的算法题——滑动窗口题目的讲解，可能有很多小伙伴会疑惑滑动窗口是个什么东西，不要着急，小编会在下面进行讲解，那么废话不多说，今天的代码时间到。

1.长度最小的子数组

1.1.题目来源

本题源自于力扣，下面给出该题链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

1.2.题目解释

首先小编还是那句话，不要被题目本身的难度所吓到，中等题不一定就意味着这个题目会很难做，就算是中等题，也会分三六九等，这个题目真的做起来，其实是不难的。这个题目想要我们去寻找一个子数组，这个数组满足它所有元素的和大于等于给定我们的数值target即可，这个题目解释起来并不难，下面小编给出这个题目的思路解析。

1.3.题目思路解析

1.3.1.暴力解法

一般我们在做算法题的时候，肯定会先想到一个通用解法：暴力解法，毕竟暴力解法是最好想出来的一个解法，就比如这个题，暴力解法其实也是很容易想起来的，我们完全可以找到所有符合条件的子数组，即数组元素加起来大于等于target，此时这个解法就是暴力解法，不用我说，各位也可以知道这个时间复杂度应该是很高的，所以这个方法是不推荐的，不过我们可以先知晓暴力解法，然后在暴力解法的基础上，进行优化，从而找到适合我们的最优解法，下面我先说说暴力解法如何把这个题目做出来，这里我就以上面的示例一为例进行讲解。

此时我们可以定义两个“指针”（这里的指针和双指针解法是一个意思），先共同指向开头。我们起名为left（代表数组的左区间），right（代表数组的右区间）。

此时我们就可以让right往后走，直到到了一个元素，使得left和right之间的元素的和为大于等于target，如下图所示：

此时我们就可以记录此时的长度，然后让left往右走一步，right回到left的位置，以此循环，我们就找到了所有的子数组，并且通过min()函数就可以找到最小的子数组，但是这种解法，各位看起来也会觉得有点冗余，下面小编给出一个解法，那就是滑动窗口解法~

1.3.2.滑动窗口解法

此时我们还是看一看上述的暴力解法，并且我们需要观察题目的条件，此时题目告知我们，这个数组存储的元素都是正整数，所以我们可以知晓，我们通过不断的对元素相加，可以知晓加起来的数是会单调递增的，所以我们可以完全借助单调性进行这个代码的优化，首先的优化：我们可以思考此时我们判断完left和right之间的元素之和大于等于target的时候，我们让left往右走的时候，此时的right是否需要回来？答案是无须回来的，因为我们可以知道此时的left和right - 1位置的数据之和肯定小于target，所以我们让left往右走之后，元素相加个数减少，此时的和会更小，所以我们无须回来，仅需让right继续往右走即可，这样做我们就可以通过减少步数减少时间复杂度，其实这个解法就是滑动窗口解法，可能很多读者朋友好奇此时为什么不叫双指针解法，它和双指针一样都用了两个指针，其实它多少也算是双指针一部分，但是，它的限制条件多：就比如此时我们是要有单调性的，这样才可以用滑动窗口，并且滑动窗口其实我们在画图的时候，就和现实中我们滑动窗口一样，如下图所示：

此时我们依据上面讲述的，通过循环我们就可以做出来这个题目了，下面在讲解代码部分之前，小编先给出一般滑动窗口题的做题步骤。

1.4.滑动窗口题目一般的做题步骤（不固定）

上面图片的内容各位读者朋友要牢记，我以后的滑动窗口题目都是以上面作为参照进行步骤书写。

1.5.代码实操

首先，我们需要先定义好两个指针（left和right），二者均为0，代表数组第一个元素，还要定义一个sum，记录此时数组的长度，一个len，保存数组的元素个数，如下所示：

int left = 0,right = 0,len = INT_MAX; //最右边这个代表着int所能存储的最大元素，为了筛选出最小值，只好让len最大了
int sum = 0;

之后，我们就要循环形成一个滑动窗口了，此时条件也是好判断的，因为我们是让right往右走，所以right的长度应该不超过数组的长度：

while(right < nums.size())
{
    
}

进入循环体，我们第一步操作就是入窗口，直接让sum += nums[right]即可，之后我们就要开始判断此时的窗口是否需要更改，此时的判断条件肯定是sum >= target的时候，此时我们就可以进行出窗口的操作，在出窗口之前，我们就要更新一下数据，因为进入了这个判断条件，我们就知道此时的子数组是合法的子数组，所以我们就要记录此时的长度，此时的len需要和之前的len进行比较，最小的留下，之后我们让左窗口向右滑动，也就是让sum减少left位置的数据，然后left右移即可，此时我可以抛出一个问题：此时这个判断我们是if判断一次好，还是while循环判断好？很显然，我们需要循环判断此时的子数组，因为有的时候，我们可能在右边入窗口的时候，进入了一个很大的数，我们出一次窗口可能不够，所以我们就需要出好几次窗口，所以我们需要循环来判断，在判断完后，让right往右走即可，下面给出这部分代码：

sum += nums[right];//进窗口
while(sum >= target)
{
    len = min(len,right - left + 1);
        sum -= nums[left];
        left++;
}
right++;

在这个循环结束以后，并不一定意味着此时我们找到了子数组，这是一个小坑，如果这个细节注意不到的话，那么此时我们代码就会报错，此时我们仅需加一个if语句判断此时的len是否还是最大的int元素即可，若是，就代表了此时并没有找到合适的子数组，返回0即可，若不是的话，我们正常返回len即可，如下所示：

if(len == INT_MAX)
{
return 0;
}
return len;

1.6.完整代码

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

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

2.1.题目来源

本题依旧来自力扣，下面我给出这个题目的链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

2.2.题目解释

本题也是很容易理解的，它就是想让我们寻找一个子串（子串就是一个字符串的一部分，就像子数组和数组之间的关系），这个子串里面的元素都是不重复的，虽然中等，但是难度不算太大（别被难度打倒了），下面给出做题的思路。

2.3.题目思路讲解

2.3.1.暴力解法

遇事不决，暴力解法，这个题目可能大部分人想到的都是暴力解法，因为暴力解法还是挺好想出来的，此时我们和上面题目一样，找到所有符合条件的子串即可，只要找倒其中最长的，返回长度即可，当然，此时我们知道重复字符的方法，还是靠眼去找的，想要在代码中体现出来，此时就借助了一个数据结构——哈希表（有一说一截止到目前我还是没学到哈希表，但是在做了一些算法题我已经会用哈希表了，各位没学过哈希表的读者朋友也不要离开，我一定会给你解释清楚的），哈希表可以存储数据元素的类型和个数，所以我们定义好两个指针，都是指向开头，然后依次把元素存放到哈希表，然后知道right位置的数据哈希表已经存放了一次了的时候，我们再进行left往后走，直到找到right位置的元素不大于1即可，再进行right回来的操作就可以，当然，这样和上面一样，right回来有点让这个代码重复了，所以我们要在这个题目的基础上进行优化算法的操作，那就是继续使用滑动窗口进行求解。

2.3.2.滑动窗口解法

本题我们依然可以使用滑动窗口的思想进行作答，此时我们在进行left右移的时候，我们可以考虑此时的right为什么不用回来，因为在right之前，left和right - 1位置的数据都是不重复的，所以此时我们无须让它回来，它回来还得回去，这样就大大增加了本题的时间复杂度了，所以我们的优化操作就是在出窗口的时候，right指针无须回来，仅需让left指针变就可以，这就是这个题目的思路讲解，其实在讲完第一个题后，相信各位堆滑动窗口的题目都有了一定的认知，所以这个题我就不细讲了，如果有不懂的读者朋友私信问小编，小编会尽自己最大努力为你解惑，下面进入代码部分。

2.4.代码实操

首先我们需要准备两个指针，用来遍历数组，它们均指向空就好，此外，正如我上面说的，我们需要用到数据结构哈希表，这里我们让hash直接以int存就好，根据字母的ASCIL值，我们可以定义128个空间，通过下标的方式来存储元素个数和类型，然后需要一个变量存储此时的子串的长度，代码如下所示：

int hash[128] = {0};  // 初始的时候让每个元素的个数都为0
int left = 0,right = 0,n = s.size();
int ret = 0;

之后，我们就进入循环部分，循环条件亘古不变，让right小于元素个数即可：

while(right < n)
{}

循环体内，我们首先就要进入入窗口的环节，此时我们就以哈希存储元素的方式入窗口即可，之后就进入判断环节，倘若此时的位置在哈希表中的个数超过1，我们就要循环的进行出窗口操作，直到left右移过程中，right位置的数据不大于1即可，此时我们可以在判断完后更新结果，因为判断的时候就代表结果是不对的；更新结果的时候我们用max()函数即可，下面给出代码：

//入窗口
hash[s[right]]++;
//判断结果
while(hash[s[right]] > 1)
{
    hash[s[left++]]--;  //出窗口操作
}
ret = max(ret,right - left + 1);
right++;

之后没什么特殊情况的话，直接返回元素个数即可（最好自己想一下有没有啥特殊情况）。

2.5.代码展示

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //本题目用的哈希表，哈希表目前我没学，所以借鉴别人的代码做出来的
        int hash[128] = {0};
        int left = 0,right = 0,n = s.size();
        int ret = 0;
        while(right < n)
        {
            //入窗口
            hash[s[right]]++;
            //判断结果
            while(hash[s[right]] > 1)
            {
                hash[s[left++]]--;  //出窗口操作
            }
            ret = max(ret,right - left + 1);
            right++;
        }
        return ret;
    }
};