样例
给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。
分析
很直观的两根指针的思路。...首先线性时间复杂度的方法,两根指针,类似滑动窗口,指向子数组的头尾,分别更新,遇到大于s就记录j-i,并且将i右移,继续寻找,这样可以找出所有的情况。...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 >=...0 : min;
}
另一种思路,我们会想到如果数组是递增的就好判断了,但这里数组是无序的,我们可以考虑计算前缀数组,那么子数组的和就是前缀数组的差了,利用二分查找
public class Solution