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: [2,3,1,2,4,3], s = 7 Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Solution: Using two pointer

    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0, sum = 0, minLen = INT_MAX;
        for (int i=0; i<nums.size(); i++) {
            sum += nums[i];
            while (sum >= s) {
                minLen = min(minLen, i-left+1);
                sum -= nums[left];
                left += 1;
            }
        }
        return minLen == INT_MAX ? 0 : minLen;
    }

Solution: Binary Search

int minSubArrayLen(int s, vector<int>& nums) {
        if (nums.empty()) return;

        int ans = INT_MAX;
        vector<int> sums(n + 1, 0); 
        //size = n+1 for easier calculations
        //sums[0]=0 : Meaning that it is the sum of first 0 elements
        //sums[1]=A[0] : Sum of first 1 elements
        //ans so on...
        for (int i = 1; i <= nums.size(); i++)
            sums[i] = sums[i - 1] + nums[i - 1];

        for (int i = 1; i <= nums.size(); i++) {
            int to_find = s + sums[i - 1];
            auto bound = lower_bound(sums.begin(), sums.end(), to_find);
            if (bound != sums.end()) {
                ans = min(ans, static_cast<int>(bound - (sums.begin() + i - 1)));
            }
        }
        return (ans != INT_MAX) ? ans : 0;
    }