[算法] 优先算法(三):滑动窗口(上)
🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:🍕 Collection与数据结构 (92平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀Java EE(94平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~
目录
- 1. 概述
- 2. 长度最小的子数组(难度:🔵2度)
- 3. 无重复字符的最长子串(难度:🔵2度)
- 4. 最大连续1的个数III(难度:🟡3度)
- 5. 将x减到0的最小操作数(难度:🟡3度)
1. 概述
所谓滑动窗口,也叫通向双指针,就是在我们上一个板块双指针的基础上,把双指针的"点"变换成"线",双指针表示两个点,而滑动窗口则是由双指针的两个"点"构成"线",表示一个区间.
滑动窗口最基本有以下几步的操作:
- 指定
left=0和right=0两个左右指针. - 让右指针右移,进入窗口.
- 让左指针右移,出窗口.
- 更新结果,结果在哪一步更新不确定,需要具体问题具体分析.
2. 长度最小的子数组(难度:🔵2度)
OJ链接
- 题目描述
给定一个含有 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
- 算法原理
由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗⼝」的思想来解决这道题。
让滑动窗⼝满⾜：从i 位置开始，窗⼝内所有元素的和⼩于target （那么当窗⼝内元素之和
第⼀次⼤于等于⽬标值的时候，就是i 位置开始，满⾜条件的最⼩⻓度）。
做法：将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：- 如果窗⼝内元素之和⼤于等于target ：更新结果，并且将左端元素划出去的同时继续判
断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件） - 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。
- 如果窗⼝内元素之和⼤于等于target ：更新结果，并且将左端元素划出去的同时继续判
- 为什么滑动窗口可以保证最终结果的正确性,而且时间复杂度很低?
- 这个窗⼝寻找的是：以当前窗口最左侧元素（记为left1 ）为基准，符合条件的情况。也
就是在这道题中，从left1 开始，满⾜区间和sum >= target 时的最右侧（记为right1 ）能到哪⾥。 - 我们既然已经找到从left1 开始的最优的区间，那么就可以大胆舍去left1 。但是如
果使用暴力解法，重新开始统计第⼆个元素（ left2 ）往后的和，势必会有⼤量重复
的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算
下次区间和的时候用上的）。 - 此时， rigth1 的作⽤就体现出来了，我们只需将left1 这个值从sum 中剔除。从
right1 这个元素开始，往后找满足left2 元素的区间（此时right1 也有可能是满
⾜的，因为left1 可能很⼩。 sum 剔除掉left1 之后，依旧满⾜⼤于等于
target ）。这样我们就能省掉⼤量重复的计算。 - 这样我们不仅能解决问题，⽽且效率也会⼤⼤提升。
时间复杂度：虽然代码是两层循环，但是我们的left 指针和right 指针都是不回退的，两者
最多都往后移动n 次。因此时间复杂度是O(N) 。 - 最后需要注意的一点就是,在一开始定义len的时候,由于题目中让我们找的是最小值,所以我们在给len赋值的时候,要赋值的是Integer的最大值.如果赋值为0,结果会一直是0.
- 这个窗⼝寻找的是：以当前窗口最左侧元素（记为left1 ）为基准，符合条件的情况。也
- 代码编写
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int right = 0;int len = Integer.MAX_VALUE;//这里之所以要定义整数的最大值,是因为后面计算最小值的//时候,如果赋值为0,就一直是0int sum = 0;for (;right < nums.length;right++){sum += nums[right];while (sum >= target){len = Math.min(len,right - left + 1);//在刚好到达最小长度的时候,更新长度//之后出窗口的时候一直更新,直到不满足循环条件sum -= nums[left];left++;}}return len == Integer.MAX_VALUE? 0:len;}
}
3. 无重复字符的最长子串(难度:🔵2度)
OJ链接
- 题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串
的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
- 算法原理
研究对象依然是一段区间,所以我们考虑使用滑动窗口.- 定义Set来统计子串中都有哪些字符.
- 每有一个字符进入窗口,就判断个字符在不在Set中.
- 如果在,就让通过移动left指针让前面的元素出窗口,每出一个,就从Set中删除一个字符,直到Set中没有right指针指向的这个字符为止.
- 如果不在,就进入窗口,让Set中也增加这个字符.
- 代码编写
class Solution {public int lengthOfLongestSubstring(String s) {Set<Character> set = new HashSet<>();//定义Set,用来统计区间内的字符int left = 0;int right = 0;int len = 0;for (;right < s.length();right++){while (set.contains(s.charAt(right))){//判断元素是否在区间中出现过set.remove(s.charAt(left));//每有元素出窗口,就从Set中删除left++;}set.add(s.charAt(right));//每有元素进入窗口,就加入Setlen = Math.max(len,right-left+1);}return len;}
}
4. 最大连续1的个数III(难度:🟡3度)
OJ链接
- 题目描述
给定一个二进制数组 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。
- 算法原理
- 这道题不要去想怎么把0转化为1
- 因此，我们可以把问题转化成：求数组中⼀段最⻓的连续区间，要求这段区间内0 的个数不超过k 个。既然是连续区间，可以考虑使⽤「滑动窗口」来解决问题。
- 让数组中的元素进入窗口,每进入一次窗口,就让表示最大长度的len++,如果进入的元素是0,那么就让统计0个数的zero++,当zero的个数大于了规定个数,就让区间之前的元素出窗口,直到0恢复正常个数.
- 代码编写
class Solution {public int longestOnes(int[] nums, int k) {int left = 0;int right = 0;int len = 0;int zero = 0;for (;right < nums.length;right++){if (nums[right] == 0){zero++;}while (zero > k){if (nums[left] == 0){zero--;}left++;}len = Math.max(len,right-left+1);}return len;}
}
5. 将x减到0的最小操作数(难度:🟡3度)
OJ链接
- 题目描述
给你一个整数数组 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 。
- 算法原理
- 这道题最不好想的一点就是:这里的区间是数组两边的两个不连续的短区间,那么我们就有一种解决问题的办法正难则反.我们可以考虑把两个短区间通过使用数组长度减去,变成一个长区间.转化成求数组内⼀段连续的、和为 sum(nums) - x 的最长数组。此时，就是熟悉的「滑动窗⼝」问题了。
- a. 转化问题：求target = sum(nums) - x 。如果target < 0 ，问题⽆解；也就是说,本用例即使把数组中所有的数字全部用上了,也达不到要求的那个值.
b. 初始化左右指针l = 0 ,r = 0 （滑动窗⼝区间表⽰为[l, r) ，左右区间是否开闭很重要，必须设定与代码⼀致），记录当前滑动窗⼝内数组和的变量sum = 0 ，记录当前满⾜条件数组的最⼤区间⻓度maxLen = -1 ；
c. 当 r ⼩于等于数组⻓度时，⼀直循环：i. 如果sum < target ，右移右指针，直⾄变量和⼤于等于target ，或右指针已经移到头；
ii. 如果sum > target ，右移左指针，直⾄变量和⼩于等于target ，或左指针已经移到
头；
iii. 如果经过前两步的左右移动使得sum == target ，修改满足条件数组的最大长度，并
让下个元素进入窗口；
d. 循环结束后，如果maxLen 的值有意义，则计算结果返回；否则，返回 -1 。
- 代码编写
class Solution {public int minOperations(int[] nums, int x) {int left = 0;int right = 0;int sum = 0;int sum1 = 0;int len = -1;for (int num:nums){sum += num;}int target = sum - x;if (target < 0){//如果数组的总和都不够达到x的,那么就不存在这样的数字//直接返回-1return -1;}for (;right < nums.length;right++){sum1 += nums[right];while (sum1 > target){sum1 -= nums[left];left++;}if (sum1 == target){len = Math.max(len,right-left+1);}}if (len == -1){return len;}else{return nums.length-len; }}
}