leetcode209.jpg

题解:

题目标签是二分查找，但给出数组是无序的，使用二分查找的方法需新建一个
sum[numberSize] 数组，sum[i] 存储 nums[0]- nums[i] 的和
因为题目给出的是正整数，这样可以确认sum 数组是单调递增的。我们只需要找到 sum[k]-sum[j]>=target ,那么k-j 便是和大于等于target且连续的子数组，当然不一定是最小的，我们需要一直查找比较。

再使用一层for循环来遍历k吗?这样效率不会比暴力算高很多，前面提过sum[] 数组是单调递增的，我们只需要将等式两边变换一下，改为 sum[k] >= sum[j]+target,这样我们每次都将target和前k项和相加作为参数传入二分查找，来取得 k (sum[j]+target的上界)。

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
33
34
35
36
37
38
39
40
41
42
//取得target的上界 
int upperBound(int* nums,int target,int numsSize){
	int l = 0;
	int r = numsSize;
	int rnIndex = -1;
	while(l<=r){
		int mid = l+(r-l)/2;
		if(nums[mid]==target){
			return mid;
		}
		if(nums[mid]>target){
			rnIndex = mid;
			r = mid-1;
		}else{
			l = mid+1;
		}
	}
	return rnIndex;
}


int minSubArrayLen(int target, int* nums, int numsSize){
	int sum[numsSize+1];
	sum[0] = 0;
	//前缀和 
	for(int i=1;i<=numsSize;++i){
		sum[i] = sum[i-1]+nums[i-1];
	}
	int len = 2147483647;
	for(int i=0;i<=numsSize;++i){
		int s = sum[i]+target;
		int index = upperBound(sum,s,numsSize);
		if(index!=-1){
			if((index-i)<len){
				len = (index-i);
			}
		}
	}
	if(len==2147483647)
		return 0;
    return len;
}

折磨了一晚上,最后的提交结果

leetcode209ac.jpg