【算法系列-数组】长度最小的子数组(滑动窗口)
文章目录
1. 长度最小的子数组(LeetCode 209)
1.1 算法分析🛸
这种求特定要求子数组的题可以使用暴力解决,但最终的时间复杂度都是比较大的(有时甚至会超时),对此,我们需要借用滑动窗口✅的方式来解决这类题:
1.2 解题思路🎯
这道题关键在于需要确定好窗口的起始位置以及终止位置,每当窗口集合的值大于目标值,就将窗口集合长度与返回值作比较,二者取最小并赋值给返回值,之后记得要将窗口的起始位置往后挪动,这一步还需要将窗口集合的值减掉起始位置移动掉的部分,即窗口缩小(窗口越小则返回值就越小),同时移动后的窗口集合的值依旧大于等于目标值的话,代表窗口还可以继续缩小,则重复上述过程,直到窗口无法缩小再移动终止位置
1.3 解题过程🎬
初始设置 返回值 ret 的长度为最大值,这样后面才能进行最小值的比较 定义 i 为 窗口起始位置,循环中的索引 j 为 窗口终止位置 进入循环后,sum += nums[j],加完后进行判断:若总和大于等于目标值target,计算出此时窗口的长度,即 j - i + 1,并与ret进行比较,取最小值并赋值给ret, 同时sum 减掉 当前窗口起始位置的值 nums[i],并将窗口起始位置向后移动一格,即 i++,若修改后的sum依旧大于等于target,重复上述过程; 若总和小于目标值target,窗口终止位置继续向后走,即 j++ ; 直到循环结束窗口终止位置遍历完,判断ret是否发生改变,发生改变则返回ret即可,否则按要求返回0
1.4 代码举例🌰
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int i = 0;
int sum = 0;
int ret = Integer.MAX_VALUE;
for (int j = 0;j < nums.length;j++) {
sum += nums[j];
while (sum >= target) {
int subLen = j - i + 1;
ret = Math.min(ret, subLen);
sum -= nums[i++];
}
}
return ret == Integer.MAX_VALUE ? 0 : ret;
}
}
2. 水果成篮(LeetCode 904)
2.1 解题思路🎯
这道题可以使用滑动窗口来解决问题,关键在于我们需要找到让窗口起始值移动的条件,那就是篮子中不同种类的水果超过2,这个时候就需要移动窗口来使篮子里的水果种类减少一种
2.2 解题过程🎬
定义一个hash表用来统计篮子里的水果种类以及数量,当map中的水果种类超过二时,通过移动窗口来减少窗口中第一个出现的水果的数量,直到第一种水果在map中被清空,退出循环,并计算最大值,重复上述过程直到窗口终止位置结束
2.3 代码举例🌰
class Solution {
public int totalFruit(int[] fruits) {
int i = 0;
Map<Integer, Integer> map = new HashMap<>();
int ret = 0;
for (int j = 0;j < fruits.length;j++) {
map.put(fruits[j], map.getOrDefault(fruits[j], 0) + 1);
while (map.size() > 2) {
int v = fruits[i++];
map.put(v, map.get(v) - 1);
if (map.get(v) == 0) {
map.remove(v);
}
}
ret = Math.max(ret, j - i + 1);
}
return ret;
}
}
以上便是对长度最小子数组类算法的介绍了!!后续还会继续分享其它算法系列内容,如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨