minimum size subarray sum

题目


思路:利用左右两个指针,分别指向Subarray的左边和右边。

如果Subarray的和大于s,更新最小的长度,减去左边的指针对应的值,将左边的指针向右移动;

如果Subarray的和小于s,将右边的指针向右移动,同时更新和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


public class Eight{
public static void main(String[] args){
System.out.println(minSubArrayLen(7, new int[]{2,3,1,2,4,3}));
}

//s > 0, and any element in nums are bigger than zero
public static int minSubArrayLen(int s, int[] nums){
if (nums == null || nums.length == 0){
return 0;
}

int length = 0;
int sum = 0;
int leftPos = 0;
int rightPos = 0;
while (rightPos <= nums.length){
if (sum >= s){
length = length == 0 ? rightPos - leftPos : Math.min(length, rightPos - leftPos);
sum -= nums[leftPos++];
}else{
if (rightPos == nums.length){
break;
}
sum += nums[rightPos++];
}
}

return length;
}
}