Question

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.

Thinking:

  • Method：brutal force
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int min = Integer.MAX_VALUE;
        int len = nums.length;
        for(int i = 0; i < len; i++){
            int count = 0;
            int sum = 0;
            for(int j = i; j < len; j++){
                sum += nums[j];
                count++;
                if(sum >= s) min = Math.min(min, count);
            }
        }
        return (min == Integer.MAX_VALUE) ? 0: min;
    }
}
  • Method 2: Two pointer
    • 快指针一直向右移动直到找到sum >= s.
    • 慢指针向右移动，不断更新最小值。
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int min = Integer.MAX_VALUE;
        int len = nums.length;
        int low = 0, high = 0;
        int sum = nums[0];
        while(high < len){
            while(sum < s){
                if(++high < len)
                    sum += nums[high];
                else break;
            }
            if(sum >= s){
                while(sum >= s && low <= high){
                    min = Math.min(min, high - low + 1);
                    sum -= nums[low];
                    low++;
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0: min;
    }
}

二刷

  1. 还是使用了双指针解决了这个问题。
  2. 如果sum >= s, 右移左指针。
  3. 如果sum < s, 右移右指针。 
    class Solution {
 public int minSubArrayLen(int s, int[] nums) {
     int len = nums.length;
     int left = -1, right = -1;
     int result = nums.length;
     int sum = 0;
     boolean flag = false;
     while(left < len){
         if(sum < s && right < len){
             if(++right >= len) break;
             sum += nums[right];
         }
         if(sum >= s){
             flag = true;
             result = Math.min(result, right - left);
             if(left < right){
                 sum -= nums[++left];
             }else return 1;
         }
     }
     return flag ? result : 0;
 }
}