LeedCode刷题---滑动窗口问题

顾得泉：个人主页

个人专栏：《Linux操作系统》??《C/C++》??《LeedCode刷题》

键盘敲烂，年薪百万！

---

一、长度最小的子数组

题目链接：长度最小的子数组?

题目描述

???????给定一个含有?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

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

解法

解法一（暴力求解)(会超时):

算法思路:

???????「从前往后」枚举数组中的任意一个元素，把它当成起始位置。然后从这个「起始位置」开始，然后寻找一段最短的区间，使得这段区间的和「大于等于」目标值。将所有元素作为起始位置所得的结果中，找到「最小值」即可。

解法二（滑动窗口):

算法思路:

???????由于此问题分析的对象是一段连续的区间，因此可以考虑「滑动窗口」的思想来解决这道题。让滑动窗口满定:从i位置开始，窗口内所有元素的和小于target(那么当窗口内元素之和第一次大于等于国标值的时候，就是i位置开始，满足条件的最小长度)。

做法:

???????将右端元素划入窗口中，统计出此时窗口内元素的和:

???????如果窗口内元素之和大于等于target:更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小，划出去之后依旧满足条件)

???????如果窗口内元素之和不满足条件: right++，另下一个元素进入窗口。

为何滑动窗口可以解决问题,并且时间复杂度更低?

???????这个窗口寻找的是:以当前窗口最左侧元素（记为left1）为基准，符合条件的情况。也就是在这道题中，从left1开始，满足区间和sum >= target时的最右侧（(记为right1)）能到哪里。

???????我们既然已经找到从left1开始的最优的区间，那么就可以大胆舍去left1。但是如果继续像方法一样，重新开始统计第二个元素(left2）往后的和，势必会有大量重复的计算（因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的)。

???????此时，rigth1的作用就体现出来了，我们只需将left1这个值从sum中剔除。从right1这个元素开始，往后找满足left2元素的区间（此时ight也有可能是满足的，因为left1可能很小。sum剔除掉left1之后，依旧满定大于等于target )。这样我们就能省掉大量重复的计算。

???????这样我们不仅能解决问题，而且效率也会大大提升。

???????时间复杂度:虽然代码是两层循环，但是我们的left 指针和right指针都是不回退的，两者最多都往后移动n次。因此时间复杂度是o(N)。

代码实现

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

---

二、无重复字符的最长字串

题目链接：无重复字符的最长子串

题目描述

???????给定一个字符串?s?，请你找出其中不含有重复字符的?最长子串?的长度。

示例?1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"????????所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"????????所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是?"wke"????????所以其长度为 3。
?    请注意，你的答案必须是 子串 的长度，"pwke"????????是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s?由英文字母、数字、符号和空格组成

解法

算法思路:

???????研究的对象依旧是一段连续的区间，因此继续使用「滑动窗口」思想来优化。让滑动窗口满足:窗口内所有元素都是不重复的。

做法:

???????右端元素ch进入茵口的时候，哈希表统计这个字符的频次:

???????如果这个字符出现的频次超过1，说明窗口内有重复元素，那么就从左侧开始划出窗口，直到ch这个元素的频次变为1，然后再更新结果。

???????如果没有超过1,说明当前窗口没有重复元素，可以直接更新结果

代码实现

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int hash[123] = {0};
        int left = 0, right = 0, ret = 0, n = s.size();
        while(right < n)
        {
            hash[s[right]]++;
            while(hash[s[right]] > 1)
                hash[s[left++]]--;
            ret = max(ret , right - left + 1);
            right++;
        }
        return ret;
    }
};

---

三、最大连续1的个数Ⅲ

题目链接：最大连续1的个数 III

题目描述

???????给定一个二进制数组?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

提示：

• 1 <= nums.length <= 105
• nums[i]?不是?0?就是?1
• 0 <= k <= nums.length

解法

算法思路:

???????不要去想怎么翻转，不要把问题想的很复杂，这道题的结果就是一段连续的1中间塞了k个0。

???????因此，我们可以把问题转化成:求数组中一段最长的连续区间，要求这段区间内的0个数不超过k个。

???????既然是连续区间，可以考虑使用「滑动窗口」来解决问题。

算法流程:

a.初始化一个大小为2的数组就可以当做哈希表hash 了;初始化一些变量left = 0，right = 0 , ret = 0;

b.当right小于数组大小的时候，一直下列循环:
?????i.让当前元素进入窗口，顺便统计到哈希表中;

???? ii.检查0的个数是否超标:

? ? ? ? ?如果超标，依次让左侧元素滑出窗口，顺便更新哈希表的值，直到的个数恢复正常;

?????iii.程序到这里，说明窗口内元素是符合要求的，更新结果;iv. right++，处理下一个元素;

c.循环结束后，ret存的就是最终结果。

代码实现

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int ret = 0;
        for(int left = 0, right = 0, zero = 0; right < nums.size(); right++)
        {
            if(nums[right] == 0) 
                zero++;    
            while(zero > k)     
                if(nums[left++] == 0) 
                    zero--;   
            ret = max(ret, right - left + 1);   
        }
        return ret;
    }
};

---

结语：今日的刷题分享到这里就结束了，希望本篇文章的分享会对大家的学习带来些许帮助，如果大家有什么问题，欢迎大家在评论区留言~~~?