Question

Formatted question description: https://leetcode.ca/all/209.html

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

 @tag-array

Algorithm

Note that this is greater than or equal to, not equal to.

Define two pointers left and right to record the left and right boundary positions of the sub-array respectively, and then move right to the right,

  • Until the sub-array sum is greater than or equal to the target value
  • Or right reaches the end of the array, At this point, update the shortest distance, and move the left image to the right by one, and then subtract the removed value from the sum, and then repeat the above steps until right reaches the end and left reaches the critical position (that is, either reaches the boundary or again move to the right), and the sum will be checked.

Code

Java

  • 
    public class Minimum_Size_Subarray_Sum {
    
        // time: O(N)
        // space: O(1)
        class Solution {
            public int minSubArrayLen(int s, int[] nums) {
    
                int i = 0; // left pointer
                int j = 0; // right pointer
    
                int minLength = Integer.MAX_VALUE;
                int sum = 0;
                for (; j < nums.length; j++) {
                    sum += nums[j];
    
                    while (sum >= s) {
    
                        minLength = Math.min(minLength, j - i + 1);
    
                        sum -= nums[i];
                        i++;
                    }
                }
    
                return minLength == Integer.MAX_VALUE ? 0 : minLength;
            }
        }
    
        // time: O(NlogN)
        // space: O(N)
        class Solution_binarySearch {
            public int minSubArrayLen(int s, int[] nums) {
                int len = nums.length;
                int[] sums = new int[len + 1];
                int res = len + 1;
    
                for (int i = 1; i < len + 1; ++i) {
                    sums[i] = sums[i - 1] + nums[i - 1];
                }
    
                // binary search
                for (int i = 0; i < len + 1; ++i) {
                    int right = searchRight(i + 1, len, sums[i] + s, sums);
                    if (right == len + 1) break;
                    if (res > right - i) res = right - i;
                }
    
                return res == len + 1 ? 0 : res;
            }
            int searchRight(int left, int right, int key, int sums[]) {
                while (left <= right) {
                    int mid = (left + right) / 2;
                    if (sums[mid] >= key) right = mid - 1;
                    else left = mid + 1;
                }
                return left;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-size-subarray-sum/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int sum = 0, i = 0, j = 0, N = nums.size(), ans = INT_MAX;
            while (j < N) {
                while (j < N && sum < s) sum += nums[j++];
                if (sum < s) break;
                while (i < j && sum >= s) sum -= nums[i++];
                ans = min(ans, j - i + 1);
            }
            return ans == INT_MAX ? 0 : ans;
        }
    };
    
  • class Solution(object):
      def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        sum = 0
        j = 0
        ans = float("inf")
        for i in range(0, len(nums)):
          while j < len(nums) and sum < target:
            sum += nums[j]
            j += 1
          if sum >= target:
            ans = min(ans, j - i)
          sum -= nums[i]
        return ans if ans != float("inf") else 0
    
    

All Problems

All Solutions