leetcode 209. Minimum Size Subarray Sum

Description:

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

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

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

1 <= target <= 1e9
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e5

两层循环就可以实现O(N^2)的解法

O(NlogN)的解法

只要把内层循环换成前缀和+二分查找就可以实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        vector<long long>sums;
        sums.resize(nums.size()+1);
        int ans = nums.size()+1;
        sums[0] = 0;
        for(int i = 1; i < nums.size()+1; ++i){
            sums[i] = sums[i-1]+nums[i-1];
        }
        for(int i = 0; i < nums.size(); ++i){
            int end = biSearch(sums,i+1,nums.size(),sums[i],target);
            if(end == -1)break;
            if(end - i < ans) ans = end-i;
        }
        if(ans == nums.size()+1) return 0;
        return ans;
    }
    int biSearch(vector<long long> &sums,int left, int right,int start_num,int target){//查找区间[left,right]
        int l = left, r = right;
        int mid;
        while(l<=r){
            mid = l+(r-l)/2;
            if(sums[mid] - start_num < target){
                l = mid+1;
                continue;
            }
            if(sums[mid-1] - start_num >= target){
                r = mid-1;
                continue;
            }
            return mid;
        }
        return -1;
    }
};

二分查找代码不长，但是容易出错、变化也挺多。与其用STL的lower/upper bound不如自己手写。

O(N)的解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = nums.size()+1;
        int l = 0,r = 0;
        long long res = 0;
        for(;;){
            while((res < target)&&(r < nums.size()))res += nums[r++];
            if(res < target) break;
            if(r - l < ans) ans = r - l;
            while((res >= target)&&(l < r)) res -= nums[l++];
            if(r - l + 1 < ans) ans = r - l + 1;//一开始把这句丢掉了
        }
        if(ans == nums.size()+1) return 0;
        return ans;
    }
};

可能是最容易想的方法。
但是我在第一遍测试发现不对之后，居然自己推翻了这个做法emmmm。。。。