LC 209 Minimum Size Subarray Sum(M)

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.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

public int minSubArrayLen(int s, int[] nums)

边界判断 数组不为空，否则直接返回0

解题思路 DP

顺序累加数值，当累加大于s时，去掉最初累加的值，直到累加小于s，同时记录当前累加的数值个数(可以通过双指针或队列来实现)，并和总计最小值比较。

队列实现

public int minSubArrayLen(int s, int[] nums) {
    if(nums.length<1)
        return 0;
    Queue<Integer> q = new LinkedList<Integer>();
    int minLen = Integer.MAX_VALUE;
    int total= 0;
    for(int i = 0; i < nums.length; i++){
        total += nums[i];
        q.offer(nums[i]);
        if(total >= s){
            while(!q.isEmpty() && total>=s){
                total -= q.poll();
            }
            minLen = Math.min(minLen, q.size() + 1);
        }
    }
    return minLen == Integer.MAX_VALUE? 0 : minLen;
}

双指针实现

public int minSubArrayLen(int s, int[] a) {
  if (a == null || a.length == 0)
    return 0;
  int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
  while (j < a.length) {
    sum += a[j++];

    while (sum >= s) {
      min = Math.min(min, j - i);
      sum -= a[i++];
    }
  }
  return min == Integer.MAX_VALUE ? 0 : min;
}