题目描述（中等难度）
找出最小的连续子数组，使得子数组的和大于等于 s。
解法一 暴力破解
从第 0 个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
从第 1 个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
从第 2 个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
...
从最后个数字开始，依次添加数字，记录当总和大于等于 s 时的长度。
从上边得到的长度中选择最小的即可。
public int minSubArrayLen(int s, int[] nums) {
int min = Integer.MAX_VALUE;
int n = nums.length;
for (int i = 0; i < n; i++) {
int start = i;
int sum = 0;
while (start < n) {
sum += nums[start];
start++;
//当前和大于等于 s 的时候结束
if (sum >= s) {
min = Math.min(min, start - i);
break;
}
}
}
//min 是否更新，如果没有更新说明数组所有的数字和小于 s, 没有满足条件的解, 返回 0
return min == Integer.MAX_VALUE ? 0 : min;
}
时间复杂度：O(n²)。
解法二 双指针
受到 76 题 Minimum Window Substring 的启示，找一个范围使得其值满足某个条件，然后就会想到滑动窗口，也就是用双指针的方法。和这道题本质是一样的。
用双指针 left 和 right 表示一个窗口。
- right 向右移增大窗口，直到窗口内的数字和大于等于了
s。进行第2步。 - 记录此时的长度，left 向右移动，开始减少长度，每减少一次，就更新最小长度。直到当前窗口内的数字和小于了
s，回到第 1 步。
举个例子，模拟下滑动窗口的过程吧。
s = 7, nums = [2,3,1,2,4,3]
2 3 1 2 4 3
^
l
r
上边的窗口内所有数字的和 2 小于 7, r 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 3 小于 7, r 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 3 + 1 小于 7, r 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 3 + 1 + 2 大于等于了 7, 记录此时的长度 min = 4, l 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 3 + 1 + 2 小于 7, r 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 3 + 1 + 2 + 4 大于等于了 7, 更新此时的长度 min = 4, l 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 1 + 2 + 4 大于等于了 7, 更新此时的长度 min = 3, l 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 4 小于 7, r 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 2 + 4 + 3 大于等于了 7, 更新此时的长度 min = 3, l 右移
2 3 1 2 4 3
^ ^
l r
上边的窗口内所有数字的和 4 + 3 大于等于了 7, 更新此时的长度 min = 2, l 右移
2 3 1 2 4 3
^
r
l
上边的窗口内所有数字的和 3 小于 7, r 右移，结束
代码的话，只需要还原上边的过程即可。
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int left = 0;
int right = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
while (right < n) {
sum += nums[right];
right++;
while (sum >= s) {
min = Math.min(min, right - left);
sum -= nums[left];
left++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
时间复杂度：O(n)。
解法三 二分查找
正常想的话，到解法二按理说已经结束了，但题目里让提出一个 O(nlog(n)) 的解法，这里自己也没想出来，分享下 这里O(NLogN)-solutions-both-O(1)-space) 的想法。
看到 log 就会想到二分查找，接着就会想到有序数组，最后，有序数组在哪里呢？
定义一个新的数组，sums[i] ，代表从 0 到 i 的累积和，这样就得到了一个有序数组。
这样做有个好处，那就是通过 sums 数组，如果要求 i 到 j 的所有子数组的和的话，就等于 sums[j] - sums[i - 1]。也就是前 j 个数字的和减去前 i - 1 个数字的和。
然后求解这道题的话，算法和解法一的暴力破解还是一样的，也就是
求出从第 0 个数字开始，总和大于等于 s 时的长度。
求出从第 1 个数字开始，总和大于等于 s 时的长度。
求出从第 2 个数字开始，总和大于等于 s 时的长度。
...
不同之处在于这里求总和时候，可以利用 sums 数组，不再需要累加了。
比如求从第 i 个数字开始，总和大于等于 s 时的长度，我们只需要找从第 i + 1 个数字到第几个数字的和大于等于 s - nums[i] 即可。求 i + 1 到 j 的所有数字的和的话，前边已经说明过了，也就是 sums[j] - sums[i]。
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] sums = new int[n];
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] = nums[i] + sums[i - 1];
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int s2 = s - nums[i]; //除去当前数字
for (int j = i; j < n; j++) {
//i + 1 到 j 的所有数字和
if (sums[j] - sums[i] >= s2) {
min = Math.min(min, j - i + 1);
}
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
至于二分查找，我们只需要修改内层的 for 循环。对于 sums[j] - sums[i] >= s2，通过移项，也就是 sums[j] >= s2 + sums[i] ，含义就是寻找一个 sums[j]，使得其刚好大于等于 s2 + sums[i]。因为 sums 是个有序数组，所有找 sum[j] 可以采取二分的方法。
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] sums = new int[n];
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] = nums[i] + sums[i - 1];
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int s2 = s - nums[i];
//二分查找，目标值是 s2 + sums[i]
int k = binarySearch(i, n - 1, sums, s2 + sums[i]);
if (k != -1) {
min = Math.min(min, k - i + 1);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
//寻求刚好大于 target 的 sums 的下标，也就是大于等于 target 所有 sums 中最小的那个
private int binarySearch(int start, int end, int[] sums, int target) {
int mid = -1;
while (start <= end) {
mid = (start + end) >>> 1;
if (sums[mid] == target) {
return mid;
} else if (sums[mid] < target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
//是否找到，没有找到返回 -1
return sums[mid] > target ? mid : -1;
}
时间复杂度：O(nlog(n))。
2020.5.30 更新，感谢 @Yolo 指出，上边的代码虽然 AC 了，但二分查找是有瑕疵的。
当 sums[mid] > target 我们不能直接更新 end = mid - 1 ，因为此时的 mid 可能是我们要找的解，所以应该改成 end = mid 。
自己构造了一个反例
59
[10, 50, 5]
这个 case 在 leetcode 是过不了的。
代码改成下边的样子就可以了。
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] sums = new int[n];
sums[0] = nums[0];
for (int i = 1; i < n; i++) {
sums[i] = nums[i] + sums[i - 1];
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int s2 = s - nums[i];
//二分查找，目标值是 s2 + sums[i]
int k = binarySearch(i, n - 1, sums, s2 + sums[i]);
if (k != -1) {
min = Math.min(min, k - i + 1);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
//寻求刚好大于 target 的 sums 的下标，也就是大于等于 target 所有 sums 中最小的那个
private int binarySearch(int start, int end, int[] sums, int target) {
int mid = -1;
while (start < end) {
mid = (start + end) >>> 1;
if (sums[mid] >= target) {
end = mid;
} else {
start = mid + 1;
}
}
//是否找到，没有找到返回 -1
return sums[start] >= target ? start : -1;
}
上边还要注意的一点是，我们要找的是大于等于 target 中最小的下标，所以当 sums[mid] == target 的时候不能立刻停止，需要继续查找。
当然这里其实不用管，因为这里的数组是累和数组，并且都是整数，是严格递增的，当找到相等的时候，前一个一定是小于 target 的。
解法四 二分查找
解法三的二分查找的关键在于 sums 数组的定义，一般情况下也不会往那方面想。还是在 这里O(NLogN)-solutions-both-O(1)-space) 看到的解法，另外一种二分的思路，蛮有意思，分享一下。
题目中，我们要寻找连续的数字和大于等于 s 的最小长度。那么，我们可以对这个长度采取二分的方法去寻找吗？
答案是肯定的，原因就是长度为 1 的所有连续数字中最大的和、长度为 2 的所有连续数字中最大的和、长度为 3 的所有连续数字中最大的和 ... 长度为 n 的所有连续数字中最大的和，同样是一个升序数组。
算法的话就是对长度进行二分，寻求满足条件的最小长度。
对于长度为 n 的数组，我们先去判断长度为 n/2 的连续数字中最大的和是否大于等于 s。
- 如果大于等于
s，那么我们需要减少长度，继续判断所有长度为n/4的连续数字 - 如果小于
s，我们需要增加长度，我们继续判断所有长度为(n/2 + n) / 2，也就是3n/4的连续数字。
可以再结合下边的代码看一下。
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int minLen = 0, maxLen = n;
int midLen;
int min = -1;
while (minLen <= maxLen) {
//取中间的长度
midLen = (minLen + maxLen) >>> 1;
//判断当前长度的最大和是否大于等于 s
if (getMaxSum(midLen, nums) >= s) {
maxLen = midLen - 1; //减小长度
min = midLen; //更新最小值
} else {
minLen = midLen + 1; //增大长度
}
}
return min == -1 ? 0 : min;
}
private int getMaxSum(int len, int[] nums) {
int n = nums.length;
int sum = 0;
int maxSum = 0;
// 达到长度
for (int i = 0; i < len; i++) {
sum += nums[i];
}
maxSum = sum; // 初始化 maxSum
for (int i = len; i < n; i++) {
// 加一个数字减一个数字，保持长度不变
sum += nums[i];
sum = sum - nums[i - len];
// 更新 maxSum
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
时间复杂度：O(nlog(n))。
总
这道题的话，通过前边刷题的经验，第一反应就想到了解法二中的双指针。如果不知道双指针的话，应该会想到解法一的暴力破解。
但对于二分查找的解法三和解法四，还是比较难想到的。不过回味完，其实二分查找的关键就是那个递增的有序数列，从而可以每次抛弃一半的可选解。