[数组二分查找] 0209. 长度最小的子数组

1. 题目链接

209. 长度最小的子数组 - 力扣（LeetCode）

2. 题目大意

描述：给定一个只包含正整数的数组 nums 和一个正整数 target。

要求：找出数组中满足和大于等于 target 的长度最小的「连续子数组」，
并返回其长度。如果不存在符合条件的子数组，返回 0。

说明：

• 1≤target≤109。
• 1≤nums.length≤105。
• 1≤nums[i]≤105。

3. 示例

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

输入：target = 4, nums = [1,4,4]
输出：1

4. 解题思路

最直接的做法是暴力枚举，时间复杂度为 O(n2)。但是我们可以利用滑动窗口的方法，在时间复杂度为 O(n) 的范围内解决问题。

用滑动窗口来记录连续子数组的和，设定两个指针：left、right，分别指向滑动窗口的左右边界，保证窗口中的和刚好大于等于 target。

1. 一开始，left、right 都指向 0。
2. 向右移动 right，将最右侧元素加入当前窗口和 window‾sum 中。
3. 如果 window‾sum≥target，则不断右移 left，缩小滑动窗口长度，并更新窗口和的最小值，直到 window‾sum<target。
4. 然后继续右移 right，直到 right≥len(nums) 结束。
5. 输出窗口和的最小值作为答案。

5. 参考代码

class Solution {

    public int minSubArrayLen(int target, int[] nums) {
        int size = nums.length;
        int ans = size + 1; // 初始化为比数组长度大1的值，方便后续判断
        int left = 0;
        int right = 0;
        int windowSum = 0;

        while (right < size) {
            windowSum += nums[right];
            // 当窗口内的和大于等于目标值时，尝试缩小窗口
            while (windowSum >= target) {
                ans = Math.min(ans, right - left + 1);
                windowSum -= nums[left];
                left++;
            }
            right++;
        }

        return ans == size + 1 ? 0 : ans;
    }
}