LeetCode/209. 长度最小的子数组

209. 长度最小的子数组

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

示例:

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

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

很直观想到的就是滑动窗口，用一个变长的框框来不断缩小区间范围，但是！暴力解法竟然也过了。前缀和+二分查找的思路其实也没啥难的，就是再创建一个前缀和数组，每次寻找前缀和大于s的区间，遍历整个前缀和数组，找到最小的区间即可

具体代码如下：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int temp = s;
            for (int j = i; j < nums.length; j++) {
                temp -= nums[j];
                if (temp <= 0) {
                    result = Math.min(result, j - i + 1);
                    continue;
                }
            }

        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

本题提示在O(N)内运行，要么是两个指针从头尾开始向中间缩，要么就是滑动窗口，显然本题用滑动窗口更加合适，创建两个指针，一个指针不断后移，让该区间所有数字和大于s，此时另一个指针从头向后移，找到让区间所有数字和第一次小于s的区间，此即为一个满足条件区间，遍历整个数组，找到最小的区间即可

具体代码如下：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0, j = 0, window = 0, result = Integer.MAX_VALUE;
        while (j < nums.length) {
          	//找到大于s的区间
            while (window < s && j < nums.length) {
                window += nums[j++];
            }

           	//找到小于s的区间
            while (i < j && window >= s) {
              	//记录此区间长度，由于每次条件不成立跳出循环时，i、j还要自增
              	//所以区间长度为 j - i
                result = Math.min(result, j - i);
                window -= nums[i++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}