【算法】滑动窗口(一)-长度最小的子数组

目录

一、题目介绍

二、算法原理

1.排必然非结果情况

1.1.2区域

(1)预证区

(2)已证区

2.滑动窗口

三、提交代码

一、题目介绍

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

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= 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; }