题目
给定一个由 n 个整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。
样例
给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。
分析
很直观的两根指针的思路。
首先线性时间复杂度的方法，两根指针，类似滑动窗口，指向子数组的头尾，分别更新，遇到大于s就记录j-i，并且将i右移，继续寻找，这样可以找出所有的情况。
代码
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;
}
另一种思路，我们会想到如果数组是递增的就好判断了，但这里数组是无序的，我们可以考虑计算前缀数组，那么子数组的和就是前缀数组的差了，利用二分查找
public class Solution {
/**
* @param nums: an array of integers
* @param s: an integer
* @return: an integer representing the minimum size of subarray
*/
public int minimumSize(int[] nums, int s) {
int[] sums = new int[nums.length + 1];
for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < sums.length; i++) {
int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
if (end == sums.length) break;
if (end - i < minLen) minLen = end - i;
}
return minLen == Integer.MAX_VALUE ? -1 : minLen;
}
private int binarySearch(int lo, int hi, int key, int[] sums) {
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (sums[mid] >= key){
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo;
}
}
