【LeetCode每日一题】LeetCode 209.长度最小的子数组
LeetCode 209.长度最小的子数组
题目描述
给定一个正整数数组 nums 和一个正整数 target，找出连续子数组的最小长度，使得子数组的和大于或等于 target。如果不存在符合条件的子数组，返回 0。
Java 实现代码
public class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int left = 0, sum = 0, minLength = Integer.MAX_VALUE;for (int right = 0; right < n; right++) {sum += nums[right]; // 扩展窗口，加入当前元素// 窗口内的和大于等于 target 时，尝试缩小窗口while (sum >= target) {minLength = Math.min(minLength, right - left + 1);sum -= nums[left]; // 移动左指针，缩小窗口left++;}}return minLength == Integer.MAX_VALUE ? 0 : minLength;}
}
解题思路
滑动窗口：使用两个指针
left和right来表示当前窗口的边界，窗口的右边界逐步扩展，直到窗口内的和大于等于target。窗口收缩：每当当前窗口的和大于等于
target时，尝试通过移动左指针（即收缩窗口）来找到最小的符合条件的子数组。每次更新最小长度。返回结果：在遍历完数组后，若未找到符合条件的子数组，则返回 0；否则返回最小长度。
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。由于每个元素最多被访问两次（一次是右指针扩展，另一次是左指针收缩），因此时间复杂度是 O(n)。
- 空间复杂度：O(1)，只用了常数级别的额外空间。
举例说明执行过程
假设输入数组
nums = [2, 3, 1, 2, 4, 3]，target = 7。
初始化：
left = 0, sum = 0, minLength = Integer.MAX_VALUE遍历右指针：
right = 0，sum = 0 + nums[0] = 2，sum = 2，不满足条件sum >= 7，继续扩展。right = 1，sum = 2 + nums[1] = 5，sum = 5，不满足条件sum >= 7，继续扩展。right = 2，sum = 5 + nums[2] = 6，sum = 6，不满足条件sum >= 7，继续扩展。right = 3，sum = 6 + nums[3] = 8，sum = 8，满足条件sum >= 7，此时子数组为[2, 3, 1, 2]，长度为 4，更新minLength = 4。收缩窗口：
- 由于满足
sum >= target，我们尝试通过移动left来缩小窗口：left = 0，sum = 8，缩小窗口，sum -= nums[0] = 8 - 2 = 6，left = 1，sum = 6，不满足sum >= 7，继续扩展右指针。继续遍历：
right = 4，sum = 6 + nums[4] = 10，满足sum >= 7，此时子数组为[3, 1, 2, 4]，长度为 4，但minLength仍然保持 4。收缩窗口：
left = 1，sum = 10，继续缩小窗口，sum -= nums[1] = 10 - 3 = 7，此时sum >= target，子数组为[1, 2, 4]，长度为 3，更新minLength = 3。继续遍历：
right = 5，sum = 7 + nums[5] = 10，满足sum >= 7，此时子数组为[1, 2, 4, 3]，长度为 4，但minLength保持为 3。收缩窗口：
left = 2，sum = 10，继续缩小窗口，sum -= nums[2] = 10 - 1 = 9，仍然满足sum >= 7，子数组为[2, 4, 3]，长度为 3，minLength保持为 3。left = 3，sum = 9，继续缩小窗口，sum -= nums[3] = 9 - 2 = 7，满足sum >= 7，子数组为[4, 3]，长度为 2，更新minLength = 2。结束遍历：
- 右指针已经遍历完整个数组，最终得到
minLength = 2。