209. Minimum Size Subarray Sum 209. Minimum Size Subarray Sum

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: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
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).  209. Minimum Size Subarray Sum

---

给定一个正整数数组和一个数s，要求从数组中找出最短的子串，使得子串的和大于等于s。
解法1，双指针法，O(n)。维护两个指针left和right，初始时都为0，我们的目标就是使[left,right)的和大于等于s。所以先right右移，直到和大于等于s，此时尝试缩小区间，即left也右移，在右移的过程中，更新最短子串长度，且累加和要减去left指向的数。这样不断的先移right，后移left，并更新最短长度。

代码如下，非常简洁易懂。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums)
    {
        int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
        while (right < n) {
            while (right < n && sum < s)
                sum += nums[right++];
            while (left <= right && sum >= s) {
                ans = min(ans, right – left);
                sum -= nums[left++];
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

本代码提交AC，用时13MS。
解法2，二分查找，O(nlgn)。我们先想想暴力方法，枚举每个left，从left开始枚举right，直到累加和第一次超过sum，更新最短长度。这样两层循环，时间复杂度是O(n^2)的。有没有办法把内层查找right的时间复杂度降低呢？
遇到子数组和的问题，马上要想到借助累加和数组。所以我们先求到原数组的累加和数组accuSum[n+1]，其中accuSum[i]等于原数组中前i-1个数之和。我们利用accuSum来循环right，对于每个left，它要找一个right，使得left和right之间的和大于等于s，也就相当于在accuSum中找一个right，使得accuSum[right]>=accuSum[left]+s，等价于accuSum[right]-accuSum[left]>=s，即left到right的累加和大于等于s。因为原数组是正整数数组，所以accuSum是递增有序的，所以我们可以在accuSum中二分查找。即查找right的复杂度降为了O(lgn)，所以总的复杂度就是O(nlgn)了。
完整代码如下：

class Solution {
private:
    int searchRight(vector<int>& accuSum, int l, int r, int target)
    {
        while (l <= r) {
            int m = l + (r – l) / 2;
            if (accuSum[m] == target)
                return m;
            else if (accuSum[m] > target)
                r = m – 1;
            else
                l = m + 1;
        }
        return l;
    }
public:
    int minSubArrayLen(int s, vector<int>& nums)
    {
        int n = nums.size(), ans = INT_MAX;
        vector<int> accuSum(n + 1, 0);
        for (int i = 1; i <= n; ++i)
            accuSum[i] = accuSum[i – 1] + nums[i – 1];
        for (int left = 0; left < n; ++left) {
            int right = searchRight(accuSum, left, accuSum.size() – 1, accuSum[left] + s);
            if (right == n + 1)
                break;
            ans = min(ans, right – left);
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

本代码提交AC，用时16MS。]]>