Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

    Example:

    1. Input: s = 7, nums = [2,3,1,2,4,3]
    2. Output: 2
    3. Explanation: the subarray [4,3] has the minimal length under the problem constraint.

    Follow up:

    If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

    题意

    给定一个正整数s和一个正整数数组nums，要求在nums中找到一个最短的连续子序列，使其和大于等于s。

    思路

    滑动窗口法(Two Pointers)：连续子数组问题很容易想到使用滑动窗口来解题。用left和right分别指向窗口的左端点和右端点，如果当前窗口内的整数和小于s，则将右端点右移来拉长窗口；如果当前窗口内的整数和大于等于s，判断其长度是否比当前结果小，是则记录，并将左端点右移来缩短窗口。重复以上步骤就能得到一个长度最短且整数和大于等于s的窗口。最坏情况下左右端点都走了一遍数组，所以时间复杂度为209. Minimum Size Subarray Sum (M) - 图1%3DO(N)#card=math&code=O%282N%29%3DO%28N%29&height=20&width=112)。

    二分查找：新建sum数组，209. Minimum Size Subarray Sum (M) - 图2，则问题转化为在数组sum中求一个连续子数组，使其末首之差大于等于s。从左向右遍历，每次固定左端点i，在右半边子数组中利用二分法找到值大于等于209. Minimum Size Subarray Sum (M) - 图3的元素sum[j]，判断长度并记录。时间复杂度为209. Minimum Size Subarray Sum (M) - 图4%0A#card=math&code=O%28NlogN%29%0A&height=20&width=77)。

    代码实现 - 滑动窗口1

    1. class Solution {
    2.     public int minSubArrayLen(int s, int[] nums) {
    3.         if (nums.length == 0) {
    4.             return 0;
    5.         }
    7.         int ans = 0;
    8.         int left = 0, right = 0;
    9.         int sum = nums[0];
    10.         while (right < nums.length) {
    11.             if (sum < s && right < nums.length - 1) {
    12.                 sum += nums[++right];
    13.             } else if (sum >= s) {
    14.                 ans = ans == 0 ? right - left + 1 : Math.min(ans, right - left + 1);
    15.                 sum -= nums[left++];
    16.             } else {
    17.                 break;    // 当右端点已经在数组的末尾且sum仍比s小时，可以直接跳出
    18.             }
    19.         }
    21.         return ans;
    22.     }
    23. }

    代码实现 - 滑动窗口2

    1. class Solution {
    2.     public int minSubArrayLen(int s, int[] nums) {
    3.         int ans = Integer.MAX_VALUE;
    4.         int sum = 0;
    5.         int left = 0;
    7.         for (int right = 0; right < nums.length; right++) {
    8.             sum += nums[right];
    9.             while (sum >= s) {
    10.                 ans = Math.min(ans, right - left + 1);
    11.                 sum -= nums[left++];
    12.             }
    13.         }
    15.         return ans == Integer.MAX_VALUE ? 0 : ans;
    16.     }
    17. }

    代码实现 - 二分查找

    1. class Solution {
    2.     public int minSubArrayLen(int s, int[] nums) {
    3.         if (nums.length == 0) {
    4.             return 0;
    5.         }
    7.         int ans = Integer.MAX_VALUE;
    8.         int[] sum = new int[nums.length];
    10.         for (int i = 0; i < nums.length; i++) {
    11.             sum[i] = i == 0 ? nums[i] : sum[i - 1] + nums[i];
    12.             // 先处理掉特殊情况
    13.             if (sum[i] >= s) {
    14.                 ans = Math.min(ans, i + 1);
    15.             }
    16.         }
    18.         // 二分查找符合条件的点
    19.         for (int i = 0; i < nums.length; i++) {
    20.             int target = s + sum[i];
    21.             int left = i + 1, right = nums.length - 1;
    22.             while (left < right) {
    23.                 int mid = (right - left) / 2 + left;
    24.                 if (sum[mid] < target) {
    25.                     left = mid + 1;
    26.                 } else {
    27.                     ans = Math.min(ans, mid - i);
    28.                     right = mid;
    29.                 }
    30.             }
    31.             if (sum[right] >= target) {
    32.                 ans = Math.min(ans, right - i);
    33.             }
    34.         }
    36.         return ans == Integer.MAX_VALUE ? 0 : ans;
    37.     }
    38. }