Leetcode 209.长度最小的子数组

209.长度最小的子数组

209. 长度最小的子数组

• 标签：数组、滑动窗口、前缀和

• 难度：中等

描述：给定一个含有 n 个正整数的数组和一个正整数 target 。

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

说明：

• 1 <= target <= 10⁹

• 1 <= nums.length <= 10⁵

• 1 <= nums[i] <= 10⁵

示例：

• 示例1

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

• 示例2

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思路

使用滑动窗口，滑动窗口需要思考三个问题：

1. 窗口涵盖的范围是什么？

2. 窗口的右指针怎么移动？什么时候停止移动？

3. 窗口的左指针怎么移动？什么时候停止移动？

题目要求返回该数组中满足其总和大于等于 target 的长度最小的连续子数组的长度，所以“问题1”窗口涵盖应该是和 大于等于 target 的连续元素。明确了窗口的涵盖范围之后，再思考一下窗口的左右指针是谁先移动。毫无疑问，应该是右指针先移动，右指针移动之后再左指针移动（如果左指针移动，那么无法确定右指针怎么移动）。

牢记窗口涵盖的是和大于等于 target的连续元素。“问题2”右指针移动使用for循环遍历数组，右指针在向右滑动的时候，窗口内元素之和变大。当窗口内元素之和大于等于target的时候，此时右指针不必继续向前滑动了，再移动的话窗口元素之和只会越来越大。此时，窗口可能不需要这么多元素，就能满足和大于等于 target，所以要开始缩小窗口，移动左指针。并且，左指针不一定只移动1次，所以左指针移动应该写在循环中。

“问题3”左指针停止移动的时候是窗口内元素之和小于target时，左指针应该停下来，停止让窗口更小。后续又应该移动右指针，让窗口再变大。

public int minSubArrayLen(int target, int[] nums) {
        int left, right, sum, result, subLen;
        left = sum = subLen = 0;
        result = nums.length + 1;
        for( right = 0; right < nums.length ; right++){
                sum += nums[right];
                while(sum >= target){
                        subLen = right - left + 1;
                        result = result < subLen ? result : subLen;
                        sum -= nums[left++];
                }
        }
        if(result == nums.length + 1)
                return 0;
        else
                return result;

}

209.长度最小的子数组 题解