【算法】滑动窗口(上)

滑动窗口

定义：滑动窗口是一种在数组或字符串等数据结构中处理子数组或子字符串问题的技术。它的核心思想是通过维护一个窗口(通常是一个连续的子数组或子字符串)，并随着问题的需要移动这个窗口，来高效地解决问题。滑动窗口技术常用于寻找最大/最小值、子数组和、字符串匹配等问题

如何理解滑动窗口

窗口的定义：窗口是一个连续的子数组或子字符串，其大小可以固定或变化
窗口的移动：窗口可以向左或向右移动，通常每次移动一个元素的位置
窗口的维护：在窗口移动的过程中，需要高效地更新窗口内的信息，例如窗口内元素的和、最大值、最小值等

使用滑动窗口的步骤

初始化窗口(进窗口)：让元素进入窗口，达到一个临界值(据题目分析)

出窗口条件：超出临界值；

出窗口；

处理结果：在窗口移动的过程中或移动结束后，根据问题的要求处理结果；

长度最小的子数组

题目链接：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

暴力解题(会超时)

解题思路：

使用一个指针遍历数组，把指针指向的位置当成起始位置。从每个初始位置开始，找到最短的区间，使得区间内的所有元素之和大于等于target。然后在众多“最短”区间内，找到更短的一个即可

解题代码：

时间复杂度：O(n^2)
空间复杂度：O(1)
public static int minSubArrayLen(int target, int[] nums) {int n=nums.length;int sum1=0;//处理所有元素和仍小于目标值的情况for(int i=0;i<n;i++){sum1+=nums[i];}if(sum1<target){return 0;}int count=0;int min=100001;for(int i=0;i<n;i++) {int sum = 0;count = 0;int j=i;while(j<n&&sum<target){sum+=nums[j];count++;j++;}if(min>count&&sum>=target){min=count;}}return min;
}

滑动窗口

由于此问题分析的对象是【一段连续的区间】，因此可以考虑【滑动窗口】的思想来解决本题。

滑动窗口其实就是在暴力解题的基础上，进行优化。在暴力解题中，我们是从每个初始位置开始，寻找最短的子数组，使得子数组内的所有元素之和大于等于target，然后从最短的子数组中寻找更短的即可。

在每次更新初始位置后，要重新寻找最短的子数组，然而这一过程会有大量的重复计算。

如下图：

滑动窗口优化：减少重复计算。

初始化窗口：从cur位置开始，让元素进入窗口，满足窗口内的所有元素之和小于target---临界条件(那么当窗口内元素之和第一次大于等于目标值时，就是cur位置开始，满足条件的最小长度)

出窗口条件：窗口内元素之和大于等于target

出窗口：sum-=nums[cur++]

如果窗口内元素之和大于等于target：更新结果，并且让cur位置处元素出窗口

如果窗口内元素之和不满足条件：dest++，让下一个元素进入窗口

解题代码：

时间复杂度：O(n)
class Solution {public int minSubArrayLen(int target, int[] nums) {int n=nums.length;int sum=0;int min=Integer.MAX_VALUE;for(int cur=0,dest=0;dest<n;dest++){sum+=nums[dest];//初始化窗口while(sum>=target){//出窗口条件min=Math.min(min,dest-cur+1);//处理结果sum-=nums[cur];//出窗口cur++;}}return min==Integer.MAX_VALUE?0:min;}
}

这里，大家可能就有疑惑了，为什么滑动窗口这里也是两层循环，它的时间复杂度却是O(n)呢？

看完下面一张图，大家就能理解了。

在最坏情况下，也不过是cur从头走到尾，走n步，dest从头走到尾，走n步(cur和dest指针是不回退的)。虽然我们是用双层循环来解决本题，但这里是不需要将cur到dest区间内的元素进行重复计算的。所以时间复杂度是O(n)

无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 - 力扣（LeetCode）

题目描述：

给定⼀个字符串 s ，请你找出其中不含有重复字符的最⻓⼦串的⻓度。

⽰例 1:

输⼊: s = "abcabcbb"

输出: 3

解释: 因为⽆重复字符的最⻓⼦串是 "abc" ，所以其⻓度为 3 。

⽰例 2:

输⼊: s = "bbbbb"

输出: 1

解释: 因为⽆重复字符的最⻓⼦串是 "b" ，所以其⻓度为 1 。

⽰例 3:

输⼊: s = "pwwkew"

输出: 3

解释: 因为⽆重复字符的最⻓⼦串是 "wke" ，所以其⻓度为 3 。

请注意，你的答案必须是⼦串的⻓度， "pwke" 是⼀个⼦序列，不是⼦串。

提⽰：

• 0 <= s.length <= 5 * 10^4

• s 由英⽂字⺟、数字、符号和空格组成 1

暴力解题(未超时)

使用两层for循环进行遍历，并用数组记录已出现字符的次数。

外层for循环用来记录初始位置，内层for循环用来找出最长子串。
当数组的某个元素大于1，就结束内层循环，得到一个最长子串。
在多个最长子串中，得到最长的即可

虽然本题也是从初始位置开始，然后一一遍历，直到找到最长子串。从下一个初始位置开始，仍会重复遍历，导致时间复杂度较高

本题不超时的原因有：字符串的元素种类只有几十个，即使每次都需要重复，但是重复的次数变少了。因此可以通过leetcode案例

解题代码：

时间复杂度:O(n^2)
class Solution {public static int lengthOfLongestSubstring(String s) {int max=0;int n=s.length();for(int i=0;i<n;i++){int count=0;int[] hash=new int[128];for(int j=i;j<n;j++){hash[s.charAt(j)]++;if(hash[s.charAt(j)]>1){break;}count++;}if(max<count){max=count;}}return max;}
}

滑动窗口

由于研究的对象依旧是【一段连续的区间】，因此可以继续使用【滑动窗口】思想来优化

让滑动窗口满足：窗口内所有元素都是不重复的

解题思路：

初始化窗口(进窗口)：满足窗口内的元素不重复的同时，让元素进入窗口

出窗口条件：窗口内的元素有重复

出窗口：左侧元素出窗口，left++，直到窗口内的元素不重复

处理结果：在每一次出完窗口后，子串的长度就是一个结果，然后在众多结果中，选择最大的；

大致流程为：

当右侧元素ch进入窗口时，用数组统计这个字符的个数：

如果这个字符的个数超过1，说明窗口内有重复元素，那么就从左侧开始划出窗口，直到ch这个元素的个数变为1

如果没有超过1，说明当前窗口内没有重复元素

解题代码：

//时间复杂度：O(n)
class Solution {public static int lengthOfLongestSubstring(String s) {int n=s.length();int[] arr=new int[128];int left=0;int right=0;int count=0;while(right<n){arr[s.charAt(right)]++;//初始化窗口while(arr[s.charAt(right)]>1){//出窗口条件arr[s.charAt(left)]--;//出窗口left++;}count=Math.max(count,right-left+1);//处理结果right++;}return count;}
}

最大连续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。
提示：

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

滑动窗口

解题思路：本题其实可以看作在一段连续的1中间塞了k个0。所以，我们只需要：找到一个最长的子数组，要求这个子数组内0的个数不超过k个

初始化窗口(进窗口)：只需要满足这个子数组内0的个数有k个即可(临界条件)

出窗口条件：子数组内0的个数刚好超过k个

出窗口：如果子数组内0的个数超过k个，则需要出窗口，直到子数组内0的个数等于k

处理结果：当子数组内0的个数小于等于k时，记录数组中连续1的个数。取最大的一个

解题代码：

//时间复杂度：O(n)
class Solution {public static int longestOnes(int[] nums, int k) {int n=nums.length;int count=0;for(int left=0,right=left;right<n;right++){if(nums[right]==0){k--;//进窗口}while(k<0){//出窗口条件if(nums[left]==0){k++;//出窗口}left++;}count=Math.max(count,right-left+1);//处理结果}return count;}
}

暴力解题

每次初始化一个起始位置，从起始位置开始向后遍历。直到该区间内0的个数等于k。记录该区间中连续1的最大个数。从多个结果中，选最大的一个。

第一次提交时，发现有一个特殊案例没有通过，如下图：

此时的代码为：

//时间复杂度：O(n)
class Solution {public static int longestOnes(int[] nums, int k) {int n=nums.length;int count=0;for(int i=0;i<n;i++){int temp=k;int j=i;for(;j<n;j++){if(nums[j]==0){temp--;}if(temp<0){count=Math.max(count,j-i);break;}}}return count;}
}

注意：有一种情况需要特别处理，即k大于数组中0的个数，此时j会继续遍历，直到等于数组长度

解题代码：

//时间复杂度：O(n)
class Solution {public static int longestOnes(int[] nums, int k) {int n=nums.length;int count=0;for(int i=0;i<n;i++){int temp=k;int j=i;for(;j<n;j++){if(nums[j]==0){temp--;}if(temp<0){count=Math.max(count,j-i);break;}}if(j==n&&k>=0)return Math.max(count, j - i);}return count;}
}

将x减到0的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目描述：

给你⼀个整数数组 nums 和⼀个整数 x 。每⼀次操作时，你应当移除数组 nums 最左边或最右边的

元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使⽤。

如果可以将 x 恰好减到 0 ，返回最⼩操作数；否则，返回 -1 。

⽰例 1：

输⼊：nums = [1,1,4,2,3], x = 5

输出：2

解释：最佳解决⽅案是移除后两个元素，将 x 减到 0 。

⽰例 2：

输⼊：nums = [5,6,7,8,9], x = 4

输出：-1

⽰例 3：

输⼊：nums = [3,2,20,1,1,3], x = 10

输出：5

解释：最佳解决⽅案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提⽰：

1 <= nums.length <= 10^5

1 <= nums[i] <= 10^4

1 <= x <= 10^9

题目分析：

本题让我们移除数组最左边或最右边的元素，再令x减去该元素的值。当x恰好减到0时，返回最小的移除个数；否则返回-1。光是看题目，感觉有些复杂。但是转化一下问题，会变得简单。

我们可以先计算出数组内元素和sum，然后在数组中找到一个区间，使得区间元素之和等于sum-x。此时剩下的区间之和就等于x。为了找到最小区间之和等于x，只需要找到最大的区间，使得区间内元素之和等于sum-x即可

为了找到【一段连续的子数组】，使得子数组的元素和等于sum-x。我们采用【滑动窗口】

滑动窗口

初始化窗口：满足区间内元素和恰好小于等于sum-x

出窗口条件：区间内元素和大于sum-x

出窗口：当子数组内元素和大于sum-x时，令左侧元素出窗口，直到满足元素和小于等于sum-x

处理结果：当子数组内元素和等于sum-x时，求出子数组长度。用数组长度减去子数组长度即得到最小操作数

注意：

当nums=[1,2]， x=3时，当整个数组和刚好等于x时，返回数组长度。但在滑动窗口中，不需要额外表示。

当nums=[3,4]，x=8时，即整个数组和都小于x时，直接返回-1

解题代码：

//时间复杂度：O(n)
class Solution {public static int minOperations(int[] nums, int x) {int n=nums.length;int count=-1;int sum=0;for(int a:nums)sum+=a;int target=sum-x;//只需要找到窗口内元素和==target即可if(target<0)return -1;int temp=0;for(int left=0,right=0;right<n;right++){temp+=nums[right];//进窗口while(temp>target){//出窗口条件temp-=nums[left++];//出窗口}if(temp==target){count=Math.max(count,right-left+1);//更新结果}}if(count==-1) return count;else return nums.length-count;}
}

暴力解题

注意：当nums=[1,2]， x=3时，当整个数组和刚好等于x时，返回数组长度。但在滑动窗口中，不需要额外表示。

//时间复杂度：O(n^2)
class Solution {public static int minOperations(int[] nums, int x) {int n=nums.length;int sum=0;for(int tmp:nums){sum+=tmp;}if(sum==x)return n;//当整个数组元素和恰好等于x时//找到一个最大区间 使得区间元素之和等于 sum-xint target=sum-x;int count=-1;if(target<0)return -1;for(int i=0;i<n;i++){int temp=0;for(int j=i;j<n;j++){temp+=nums[j];if(temp>target){break;}if(temp==target){count=Math.max(count,j-i+1);break;}}}if(count==-1)return count;return n-count;}
}