LeetCode: 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^2) solution, 
try coding another solution of which the time complexity is O(n log n). 

解题思路 —— 前序和+二分查找

先求得前序和，然后根据前序和，二分查找出满足要求的最短的连续子数组。

AC 代码

class Solution {
    // [beg, end)
    int binarySearch(const vector<int>& frontSum, int beg, int end, int target)
    {
        if(beg >= end) return beg;
        
        int mid = (beg+end)/2;
        if(frontSum[mid] == target) return mid;
        else if(frontSum[mid] > target) return binarySearch(frontSum, beg, mid, target);
        else return binarySearch(frontSum, mid+1, end, target);
    }
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.empty()) return 0;
        
        // 前序和
        vector<int> frontSum;
        for(int i = 0; i <= nums.size(); ++i)
        {
            if(i == 0) frontSum.push_back(0);
            else frontSum.push_back(nums[i-1]+frontSum.back());
        }
        
        int minLen = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            // 二分查找
            int idx = binarySearch(frontSum, i+1, frontSum.size(), frontSum[i]+s);
            if(idx < frontSum.size() && (minLen == 0 || minLen > idx-i))
            {
                minLen = idx -i;
            }
        }
        
        return minLen;
    }
};