Smallest Subarray with a given sum (easy)

Problem Statement#

Given an array of positive numbers and a positive number ‘S,’ find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’. Return 0 if no such subarray exists.

Example 1:

Input: [2, 1, 5, 2, 3, 2], S=7 Output: 2Explanation: The smallest subarray with a sum greater than or equal to '7' is [5, 2].

Example 2:

Input: [2, 1, 5, 2, 8], S=7 Output: 1Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].

Example 3:

Input: [3, 4, 1, 1, 6], S=8 Output: 3Explanation: Smallest subarrays with a sum greater than or equal to '8' are [3, 4, 1] or [1, 1, 6].

类型：动态滑动窗口

找出比S大的最短子数组

  public static int findMinSubArray(int S, int[] arr) {
        if (S <= 0 || arr == null || arr.length == 0) {
            return -1;
        }
        int sum = 0;
        int result = Integer.MAX_VALUE;
        int start = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            while (sum >= S) {
                result = Math.min(result, i - start + 1);
                sum -= arr[start++];
            }
        }
        return result != Integer.MAX_VALUE ? result : -1;
  }