LeetCode209:MinSubArrayLen
![](https://bu.dusays.com/2023/10/30/653f6b1187106.png)
LeetCode209:MinSubArrayLen
SerMs
坚持就是胜利
LeetCode地址
滑动窗口解题思路
初始化变量和窗口
- 定义两个指针 left 和 right,分别表示窗口的左右边界,初始化为0。
- 定义一个变量 sum 用于存储窗口内元素的和,初始值为0。
- 定义一个变量 minlength 用于记录符合条件的最短子数组的长度,初始值为0。
移动右边界,扩大窗口
- 在一个 while 循环中,不断将 nums[right] 加到 sum 中,然后将右指针 right 向右移动,扩大窗口。
移动左边界,缩小窗口
- 如果当前窗口的和大于等于目标值 target,则在另一个内部的 while 循环中,不断将 nums[left] 从 sum 中减去,并将左指针 left 向右移动,缩小窗口,直到窗口内的和小于目标值。
- 在这个过程中,不断更新 minlength,保持其为符合条件的最短子数组的长度。
循环直到右指针到达数组末尾
- 不断执行步骤2和步骤3,直到右指针 right 到达数组的末尾。
返回结果
- 返回 minlength,即为符合条件的最短子数组的长度。
代码展示
1 | public static int minSubArrayLen(int target, int[] nums) { |
双指针解题思路
初始化变量和窗口
- size 表示数组的长度,ans 用于记录符合条件的最短子数组的长度,初始化为 size + 1,确保初始值大于任何可能的子数组长度。
- l 表示窗口的左边界,初始化为0。
- sum 表示窗口内元素的和,初始化为0。
移动右边界,扩大窗口
- 使用一个 for 循环,遍历数组,移动右指针 r,将 nums[r] 加到 sum 中,扩大窗口。
移动左边界,缩小窗口
- 在一个内部的 while 循环中,如果当前窗口的和大于等于目标值 target,则计算当前子数组的长度 r - l + 1,并更新 ans 为较小的值,即 Math.min(ans, r - l + 1)。
- 然后将窗口的左边界向右移动,即 sum -= nums[l++],缩小窗口。
循环直到右指针到达数组末尾
- 不断执行步骤2和步骤3,直到右指针 r 到达数组的末尾。
返回结果
- 返回 ans,即为符合条件的最短子数组的长度。如果 ans 的值没有被更新,说明没有符合条件的子数组,返回0。如果您还有更好的解题思路请在下方评论区交流
1
2
3
4
5
6
7
8
9
10
11
12
13// 双指针
public static int minSubArrayLen03(int target, int[] nums) {
int left = 0, right = 0, min = Integer.MAX_VALUE, sum = 0;
while (right < nums.length) {
sum += nums[right];
while (sum >= target) {
min = Math.min(min, right - left + 1);
sum -= nums[left++];
}
right++;
}
return min <= nums.length ? min : 0;
}
评论
匿名评论隐私政策
✅ 你无需删除空行,直接评论以获取最佳展示效果