【算法】滑动窗口(一)-长度最小的子数组
目录
一、题目介绍
给定一个含有 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 <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
二、算法原理1.排必然非结果情况1.1.2区域(1)预证区
预证区 排能确(2)已证区
已证区 排能确
3. 无重复字符的最长子串 - 力扣（LeetCode）
2.滑动窗口
两指针排算情况 同向不退地 维护着 头尾同向滑动的窗口
三、提交代码
public int minSubArrayLen(int target, int[] nums) { int n = nums.length, sum = 0, len = Integer.MAX_VALUE; for(int left = 0, right = 0; right < n; right++) { // 越界时退出条件，隔开来了 sum += nums[right]; //进窗口 // 用外层的for循环来进行 连续进窗口，少一个循环体 // 出窗口 与 更新结果 条件一样 while(sum >= target) { //判断 // 上面进窗口-大于时退出条件 与 下面出窗口-大于时进入条件 共用一个 也是隔开了了 ; 都是要在进窗口 判断完之后 才能更新结果： len = Math.min(len, right - left + 1); //(一定是进窗口后、判断完后)出窗口时更新结果 // 一步符合就去更新一次，不能等全部出完在外面更新，因为如果到循环外面不符合时再去更新的话，它的这个位置 已经被right不符合的 在一起占了，如果要放一起 要额外的判断： sum -= nums[left++]; } //更新结果如果放外面的额外判断： //进过循环 之前大于target 去减了元素而退出，在循环里面放一个标志位，然后可以统计结果 //没进循环，就是正常+nums[right]后还是小于target的，不统计结果 } return len == Integer.MAX_VALUE ? 0 : len; }
