209.Minimum Size Subarray Sum

Tags: Medium Array Two Pointers Binary Search

Links: https://leetcode.com/problems/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).

---

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        vector<int> preSum(n + 1);
        for (int i = 1; i <= n; ++i) {
            preSum[i] = nums[i - 1] + preSum[i - 1];
        }    
        if (preSum.back() < s) return 0;

        int res = INT_MAX;
        for (int i = 1; i <= n; ++i) {
            int target = preSum[i - 1] + s;
            int m = solve(preSum, target);
            res = min(res, m - i + 1);
        }
        return res;
    }

    int solve(vector<int> & preSum, int target)
    {
        if (preSum.back() < target) return INT_MAX;
        int n = preSum.size();
        int left = 0, right = n;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (preSum[mid] < target) left = mid + 1;
            else right = mid;
        }

        return left;
    }
};

《挑战程序设计竞赛》尺取法第一题。时间复杂度是$O(n \log n)$，其实还可以进一步的优化到$O(n)$。