Leetcode 209. Minimum Size Subarray Sum

Question

Find the smallest continuous sub-array such that the sum of the sub-arrays is greater than or equal to s.

Solution - Brute Force

Starting from the 0th number, add numbers in sequence, and record the length when the sum is greater than or equal to s.

Starting from the first number, add numbers in sequence, and record the length when the sum is greater than or equal to s.

Starting from the second number, add numbers in sequence, and record the length when the sum is greater than or equal to s.

Starting from the last number, add numbers in sequence, and record the length when the sum is greater than or equal to s.

Choose the smallest length from the length obtained above.

Time complexity: O (n²)

Solution - Two Pointers

Use two pointers left and right to indentify a window.

Move the right forward to increase the window until the number in the window is greater than or equal to s. Go to step 2.
Record the length at this time, move left forward, and begin to decrease the length, and each time it decreases, the minimum length is updated. Until the sum in the current window is less than s, go back to step 1.

For example, lets’ simulate the process of sliding windows:

s = 7, nums = [2,3,1,2,4,3]

2 3 1 2 4 3
^
l
r
The sum of all numbers in the upper window 2 is less than 7, so r moves forward

2 3 1 2 4 3
^ ^
l r
The sum of all numbers in the upper window 2 + 3 is less than 7, so r moves forward


2 3 1 2 4 3
^   ^
l   r
The sum of all numbers in the upper window 2 + 3 + 1 is less than 7, so r moves forward

2 3 1 2 4 3
^     ^
l     r
The sum of all numbers in the upper window 2 + 3 + 1 + 2 is greater than 7, record the length min = 4, l moves forward

2 3 1 2 4 3
  ^   ^
  l   r
The sum of all numbers in the upper window 3 + 1 + 2 is less than 7, so r moves forward

2 3 1 2 4 3
  ^     ^
  l     r
The sum of all numbers in the upper window 3 + 1 + 2 + 4 is greater than 7, record the length min = 4, l moves forward

2 3 1 2 4 3
    ^   ^
    l   r
The sum of all numbers in the upper window 1 + 2 + 4 is greater than or equal to 7, record the length and update min = 3, l moves forward

2 3 1 2 4 3
      ^ ^
      l r
The sum of all numbers in the upper window 2 + 4 is less than 7, so r moves forward

2 3 1 2 4 3
      ^   ^
      l   r
The sum of all numbers in the upper window 2 + 4 + 3 is greater than or equal tp 7, record the length and update min = 3, l moves forward

2 3 1 2 4 3
        ^ ^
        l r
The sum of all numbers in the upper window 4 + 3 is greater than or equal tp 7, record the length and update min = 2, l moves forward

2 3 1 2 4 3
          ^
          r
          l
The sum of all numbers in the upper window 3 is less than 7, so r moves forward，end

public int minSubArrayLen(int s, int[] nums) {
    if (nums.length == 0) {
        return 0;
    }

    // result
    int result = Integer.MAX_VALUE;

    // 2 pointers
    int left = 0;
    int right = 0;
    int sum = 0;

    while (right < nums.length) {
        // moving right pointer forward until sum >= s
        sum += nums[right];
        right++;

        // if sum >= s, start moving left forward until sum < s
        while (sum >= s) {
            result = Math.min(result, right - left);

            sum -= nums[left];
            left++;
        }
    }

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

Time complexity: O(n)

Question

Similar Questions

Solution - Brute Force

Solution - Two Pointers