Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return -1 instead.

Have you met this question in a real interview?

Yes

Example

Given the array[2,3,1,2,4,3]and s =7, the subarray[4,3]has the minimal length under the problem constraint.

Challenge

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

line 25
line 19, needs to do every time sum >= s , otherwise may lose some result
can do using two pointers without allocation memory in deque

two pointer method line 17 j - i not j - i + 1
line 21 len not sum

class Solution {

public:

/\*\*

 \* @param nums: a vector of integers

 \* @param s: an integer

 \* @return: an integer representing the minimum size of subarray

 \*/

int minimumSize\(vector<int> &nums, int s\) {

    // write your code here

    if \(nums.empty\(\)\) {

        return -1;

    }



    int len = INT\_MAX;

    int j = 0, sum = 0;

    for \(int i = 0; i < nums.size\(\); ++i\) {

        while \(sum < s && j < nums.size\(\)\) {

            sum += nums\[j\];

            ++j;

        }

        if \(sum >= s\) {

            if \(j - i < len\) {

                len = j - i;

            }

            sum -= nums\[i\];

        }

    }

    if \(len == INT\_MAX\) {

        return -1;

    }

    return len;

}

};

results matching ""

    No results matching ""