209. 长度最小的子数组

问题

给定一个含有 $n$ 个正整数的数组和一个正整数 $s$ ，找出该数组中满足其和 $≥ s$ 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 $0$ 。

示例:

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

进阶:

如果你已经完成了 $O(n)$ 时间复杂度的解法, 请尝试 $O(n log n)$ 时间复杂度的解法。

解法

连续子数组，考虑使用双指针 $start$ 与 $end$ 滑动窗口来判断.设置一个 $sum$ 值，表示滑动窗口中的和，每一轮循环，判断 $sum$ 与 $s$ 的关系，有两种情况：

$sum$ 大于等于 $s$ ，此时 $sum$ 减去 $start$ 指针所指向的值， $start$ 指针前进。
$sum$ 小于 $s$ ，此时， $sum$ 加上 $end$ 的值， $end$ 指针前进。

代码

java实现

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        // 注意这里的end的起始位置
        int start = 0, end = -1;
        int result = Integer.MAX_VALUE, sum = 0;
        // 开始循环，循环跳出的条件是start指针循环到数组尾部了
        while (start < nums.length) {
            // 这里需要注意判断条件
            if (sum < s && end + < nums.length) {
                end++;
                sum += nums[end];            
            } else {
                sum -= nums[start];
                start++;
            }
            if (sum >= s) result = result < end - start + 1 ? result : end - start + 1;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}