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).

用2 pointers來達到sliding window的方法，利用一個變數sum來紀錄當前的總和，如果發現大於等於s，那麼就要從頭的部分開始往後縮，start開始往前走。

// Sliding Window Method
int minSubArrayLen(int s, vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size(), start = 0, sum = 0, minLen = numeric_limits<int>::max();
    for (int i = 0; i < n; ++i) {
        sum += nums[i];
        while (sum >= s) {
            minLen = min(minLen, i - start + 1);
            sum -= nums[start++];
        }
    }
    return minLen == numeric_limits<int>::max() ? 0 : minLen;
}

// Sliding window
int minSubArrayLen(int s, vector<int>& nums) { // time: O(n); space: O(1)
    int n = nums.size(), begin = 0, end = 0, sum = 0, res = numeric_limits<int>::max();
    while (end < n) {
        sum += nums[end++];
        while (sum >= s) {
            res = min(res, end - begin);
            sum -= nums[begin++];
        }
    }
    return res == numeric_limits<int>::max() ? 0 : res;
}

用Binary search來達到follow-up的要求time complexity。也有點類似sliding window的方法，i在for loop內開始掃過每個sliding window的end position，如果發現sums[i]大於等於s之後，就可以用binary search去找出accumulative sum array中，大於sums[i] - s的位置p，如果這個位置存在，i - p + 1就是這一段符合條件的長度。

// Binary Search Method
vector<int> accumulate(const vector<int>& nums) {
    int n = nums.size();
    vector<int> sums(n + 1);
    for (int i = 1; i <= n; ++i) {
        sums[i] = sums[i - 1] + nums[i - 1];
    }
    return sums;
}
int upperBound(const vector<int>& sums, int left, int right, int target) {
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (sums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return sums[right] > target ? right : -1;
}
int minSubArrayLen(int s, vector<int>& nums) { // time: O(nlogn); space: O(n)
    const vector<int>& sums = accumulate(nums);
    int n = nums.size(), minLen = numeric_limits<int>::max();
    for (int i = 1; i <= n; ++i) {
        if (sums[i] >= s) {
            int p = upperBound(sums, 0, i, sums[i] - s);
            if (p != -1) minLen = min(minLen, i - p + 1);
        }
    }
    return minLen == numeric_limits<int>::max() ? 0 : minLen;
}