首页 > itarticle > [leetcode] problem 209 – minimum size subarray sum

[leetcode] problem 209 – minimum size subarray sum

admin 11月 13, 2020 0

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

Code

public int (int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    int sum = 0;

    for (int left = 0, right = 0; right < nums.length; right++) {
        sum += nums[right];

        while (sum >= s) {
            min = Math.min(min, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return min == Integer.MAX_VALUE ? 0 : min;
}