【算法】【优选算法】滑动窗口（上）
目录
- 一、滑动窗口简介
- 二、209.⻓度最⼩的⼦数组
- 2.1 滑动窗口
- 2.2 暴力枚举
- 三、3.⽆重复字符的最⻓⼦串
- 3.1 滑动窗口
- 3.2 暴力枚举
- 四、1004.最⼤连续1的个数III
- 4.1 滑动窗口
- 4.2 暴力枚举
- 五、1658.将x减到0的最⼩操作数
- 5.1 滑动窗口
- 5.2 暴力枚举
一、滑动窗口简介
其实就是利用单调性，使用同向双指针来优化暴力枚举的一种算法。
我们遇到这种题的解法就找如下四个东西：
- 进窗口；
- 出窗口条件；
- 出窗口；
- 修改结果语句，修改结果语句的位置是不固定的，但上面3个东西的顺序是固定由上到下。
二、209.⻓度最⼩的⼦数组
题目链接：209.⻓度最⼩的⼦数组
题目描述：
题目解析：
- 这个数组中都是正整数；
- 在数组中找两个元素和大于等于目标值的最小长度（即下标之差加1）。
2.1 滑动窗口
解题思路：
- 我们使用sum来记录[left, right]区间中元素的和，
- 由于题目中说给的元素都为正整数，所以我们left像后走就是将sum减小，而right向后走就是将sum变大。
- 所以我们进窗口就是求和 sum += nums[right]。
- 出窗口条件sum >= target，由于出去一个元素，可能sum还是比目标值大，所以这里要使用循环。
- 出窗口就是sum -= nums[left++]。
- 修改结果就是求ret 与现在的长度的最小值Math.min(ret, right-left+1)。
- 这道题的细节问题，由于我们求得长度的最小值，所以初始化结果的时候要使用一个较大的值。
解题代码：
//时间复杂度O(N)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ret = 0x3f3f3f3f;
int sum = 0;
for(int left = 0, right = 0; right < nums.length; right++) {
sum += nums[right];//进窗口
while(sum >= target) {//判断条件
ret = Math.min(ret, right-left+1);//修改结果
sum -= nums[left++];//出窗口
}
}
return ret == 0x3f3f3f3f ? 0 : ret;
}
}
2.2 暴力枚举
解题思路：
- 我们直接使用两层for循环将所有可能枚举出来。
- 会超时。
解题代码：
//时间复杂度O(N^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ret = 0x3f3f3f3f;
for(int i = 0; i < nums.length; i++) {
int sum = nums[i];
if(sum >= target) return 1;
for(int j = i+1; j < nums.length; j++) {
sum += nums[j];
if(sum >= target) {
ret = Math.min(ret, j-i+1);
}
}
}
return ret == 0x3f3f3f3f ? 0 : ret;
}
}
三、3.⽆重复字符的最⻓⼦串
题目链接：3.⽆重复字符的最⻓⼦串
题目描述：
题目解析：
-题目要求给得十分清晰，只要我们返回字符串中连续不相同字符构成的子串的长度的最大值即可。
3.1 滑动窗口
解题思路：
- 当我们已经拿到一个子串，以例1的abcabcbb为例，当我们拿到子串abc的时候下一个是a,我们只需要将子串的起点将重复字符走过就行，所以我们的子串前后都往同一个方向走，使用滑动窗口。
- 要记录下子串中每个字符的个数，使用hash表的性质，只有一个相同元素，这里的元素是知道的只有ASCII码表中的，直接使用一个数组代替即可，当前子串中元素对应下标的hash[ ]数组的值就是当前子串中含有该元素的个数。
- 进窗口：就是把每个字符的对应hash数组的元素加一；
- 出窗口条件：当我们现在进入字符后，hash数组中值大于1；
- 出窗口：循环出一直出到重复的字符为止。
- 更新结果：每一次出完了窗口之后的子串就是一个符合条件的子串，只需要求它的长度与原结果的较大值即可。
解题代码：
//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int left = 0, right = 0, ret = 0;
int[] hash = new int[128];
while(right < len) {
hash[s.charAt(right)]++;//进窗口
while( hash[s.charAt(right)] > 1) {//出窗口条件
hash[s.charAt(left++)]--;//出窗口
}
ret = Math.max(ret, right - left + 1);//更新结果
right++;
}
return ret;
}
}
3.2 暴力枚举
解题思路：
- 我们只需要使用两层for循环将每一个连续不相同字符构成的子串枚举出来，然后取最大长度即可。
- 使用hash表的性质，只有一个相同元素，这里的元素是知道的只有ASCII码表中的，直接使用一个数组代替即可，当前子串中元素对应下标的hash[ ]数组的值就是当前子串中含有该元素的个数。
解题代码：
//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
int ret = 0;
for(int i = 0; i < len; i++) {
int[] hash = new int[128];
for(int j = i; j < len; j++) {
hash[s.charAt(j)]++;
if(hash[s.charAt(j)] > 1) {
break;
}
ret = Math.max(ret, j - i + 1);
}
}
return ret;
}
}
四、1004.最⼤连续1的个数III
题目链接：1004.最⼤连续1的个数III
题目描述：
题目解析：
- 题目给的翻转0，其实意思就是最多有k个0可以变成1，让连续的1的个数最大。
4.1 滑动窗口
解题思路：
- 这道题求解翻转后子数组中1最多的个数，其实也就是求子数组中<= k个0时的最大长度。
- 我们只需要使用一个计数器来记录当前子数组中的0的个数。
- 当我们的计数器没超过k的时候我们需要子数组尾一直向后走，让元素进入子数组，当超过k的时候我们又需要子数组头向后走，出元素让子数组中0的个数小于k，所以这又是一个都向后走的同向双指针问题。
- 进窗口：right向后走一步进一个元素，并判断是否是0更新计数器。
- 出窗口条件：计数器中0个数大于k。
- 出窗口：left++循环直到计数器0个数小于等于k。
- 更新结果：在出完窗口之后，子数组满足条件，就更新结果，取原结果与新数组长度较大值。
解题代码：
//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int longestOnes(int[] nums, int k) {
int len = nums.length;
int ret = 0;
int numZero = 0;
for(int left = 0, right = 0; right < len; right++) {
//进窗口
if(nums[right] == 0) numZero++;
while(numZero > k) {//出窗口条件
//出窗口
if(nums[left] == 0) numZero--;
left++;
}
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}
4.2 暴力枚举
解题思路：
- 直接两层for循环将每一个0的个数<= k的子数组列举出来。
- 细节处理，当我们遇到像这样的序列 [0,0,0,1] k = 4 我们在遍历完数组后都没有超过k，这时我们的长度就是数组长度，可能会有疑惑为啥在最后返回时使用三目运算符 ret == 0 ? nums.length : 0；不就可以了吗，但是如果是[0,0,0,0] k = 0这样的长度本来就该返回0的也会冲突，所以这两种情况我们要处理一种。
解题代码：
//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int longestOnes(int[] nums, int k) {
int ret = 0;
int numZero = 0;
for(int i = 0; i < nums.length; i++) {
int j = i;
numZero = 0;
for(; j < nums.length; j++) {
if(nums[j] == 0) numZero++;
if(numZero > k) {
ret = Math.max(ret, j - i);
break;
}
}
if(j == nums.length && numZero <= k) return Math.max(ret, j - i);
}
return ret;
}
}
五、1658.将x减到0的最⼩操作数
题目链接：1658.将x减到0的最⼩操作数
题目描述：
题目解析：
- 注意每一步操作都可以删除数组头和数组尾，让删掉的数组元素和刚好等于x，取删掉的数组元素个数最小值。
- 注意提示的数组元素都是大于0的。
- 按照题目给的操作，我们每一次的删除都是有两个选择的，这样的不确定性太高，解题非常困难。那么“正难则反”，我们就先求中间的子数组的和，然后用nums的和，减去子数组的和，这个值就是该删除的元素的和了。
5.1 滑动窗口
解题思路：
- 其实按照上面的思路，又由于数组元素都是正数，要让被删除元素和变大，只需要将中间子数组的头向后走即可，
- 而让被删除元素和变小，只需要将中间子数组的尾向后走即可。又是同向双指针问题。
- 进窗口：right向后走一步进一个元素。
- 出窗口条件：当删掉元素和大于x的时候出窗口。
- 出窗口：left++循环直到删除元素和小于等于x。
- 更新结果：在出完窗口之后，判断删除元素和是否等于x，是就更新结果，取原结果与被删除元素个数较小值。
- 但是有两种情况没考虑：
-
- 当我们的整个数组和刚好等于x的时候[4,5] x = 9。
-
- 当我们的整个数组和刚都小于x的时候[4,5] x = 8。
- 这两种情况都有可能导致出窗口条件判断的时候，使数组越界，所以判断条件中还要加上left <= right。
解题代码：
//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int minOperations(int[] nums, int x) {
int len = nums.length;
int ret = 0x3f3f3f3f;
int sum = 0;
//求和
int sumNums = 0;
for(int i = 0; i < len; i++) {
sumNums += nums[i];
}
for( int left = 0, right = 0; right < len; right++) {
sum += nums[right];//进窗口
while(left <= right && sumNums - sum < x) {//出窗口条件
sum -= nums[left++];//出窗口
}
if(sumNums - sum == x) {
ret = Math.min(ret, len - (right - left + 1) );//更新结果
}
}
return ret == 0x3f3f3f3f ? -1 : ret;
}
}
5.2 暴力枚举
解题思路：
- 直接使用两层for循环来将每一个子数组的可能枚举出来。
- 当当前的子数组的和与数组nums元素和的差值等于x的时候，就可以更新结果。
- 还是上面的整个数组和刚好等于x的时候没处理：
-
- 等于时直接在前面求和时判断返回即可。
-
- 小于在最后使用三目运算符即可。
- 会超时。
解题代码：
//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
public int minOperations(int[] nums, int x) {
int len = nums.length;
int ret = 0x3f3f3f3f;
//求和
int sumNums = 0;
for(int i = 0; i < len; i++) {
sumNums += nums[i];
}
if(sumNums == x) return len;
for(int i = 0; i < len; i++) {
int sum = 0;
for(int j = i; j < len; j++) {
sum += nums[j];
if( (sumNums - sum) == x) {
ret = Math.min(ret, len - (j - i + 1));
break;
}
}
}
return ret == 0x3f3f3f3f ? -1 : ret;
}
}