209 长度最小的子数组
前言：本篇文章是我自己解题的思路，二分查找法并没有看懂，只有一般的滑动窗口法。
滑动窗口要找出左边界和右边界变化的条件。个人理解：左边界变化的条件是max，也就是窗口内部数字的和大于等于s的时候。右边界变化的条件是小于s。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public int minSubArrayLen(int s, int[] nums) {
int max=0,result=Integer.MAX_VALUE,i=0,j=0;
while(j<nums.length) {
max=sumArray(nums,i,j);
if(max>=s) {
result=Math.min(result, j-i+1);
i++;
}else {
j++;
}
}
if(result==Integer.MAX_VALUE)return 0;
return result;
}
public int sumArray(int[]num,int start,int end) {
int sum=0;
for(int i=start;i<=end;i++) {
sum+=num[i];
}
return sum;
}
|
这么写很慢，用了89ms，题解给出了一种方式，可以在求和数组的方法上面优化一下。用一个数储存，每次变化的时候不用重新求和。
更改之后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public int minSubArrayLen(int s, int[] nums) {
int max=0,result=Integer.MAX_VALUE,i=0,j=0;
if(nums.length==0)return 0;
max+=nums[0];
while(j<nums.length) {
if(max>=s) {
result=Math.min(result, j-i+1);
max=max-nums[i];
i++;
}else {
j++;
if(j<nums.length)
max+=nums[j];
}
}
if(result==Integer.MAX_VALUE)return 0;
return result;
}
|
这个结果是2ms，鉴于二分法和我的思路查的有点多，也没看懂，所以这道题就先这样吧。leetcode 3/100