和至少为 K 的最短子数组详解Shortest Subarray with Sum at Least K #41
Description
Flag还是要立的，虽然有被疯狂打脸的风险，但是当你知道有人看到了你的Flag之后，你会比平常更加努力。元旦的时候，和老婆一起定了2019的目标，我的其中就包含了leetcode上按照通过率排序最低的50个题，这不是第一个就遇到了很大问题，看答案都看的模模糊糊的，好在互联网上总有各种先人的足迹，只要下功夫，总能通过网络上的蛛丝马迹找到想要的东西，包括自己的失踪的女儿，参考《网络谜踪》。好了，闲话就到这里，下面看原题：
题目
返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1 。
示例 1：
输入：A = [1], K = 1
输出：1
示例 2：
输入：A = [1,2], K = 4
输出：-1
示例 3：
输入：A = [2,-1,2], K = 3
输出：3
提示：
1 <= A.length <= 50000-10 ^ 5 <= A[i] <= 10 ^ 51 <= K <= 10 ^ 9
暴力解法
很多算法在算力足够的情况下，都是可以用暴力循环的方式求解，只要能够用计算机语言描述问题，就可以用暴力方式求解，比如这个题，我们就可以用下面的三层循环来求解
class Solution {
public int shortestSubarray(int[] A, int K) {
int minLen = A.length + 1;
for (int i = 0; i < A.length; i++) {
for (int j = i; j < A.length; j++) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += A[k];
}
if (sum >= K && (j - i + 1) < minLen) {
minLen = j - i + 1;
}
}
}
return minLen == A.length + 1 ? -1 : minLen;
}
}当然暴力解法也不一定就非常容易，也是有很多地方需要注意的，比如上面的第二层循环即j的那一层，我就花了点时间的，刚开始的初始条件是int j = i + 1，但是对于上面的示例1就通过不了，因为这种写法默认输入是包含两个及以上元素的，但是实际情况是我们常常会遇到1个甚至是空的输入这种边界条件，而且对这些条件的处理往往才是实现代码时的关键点。
暴力解法最大的问题就在于时间开销太大，在一些输入规模比较大的情况下，基本上没有用，相当于这个问题没有解决，比如我们上面这种暴力解法，其时间负责度就是O(n^3)，但是它又一个好处是空间复杂度比较低，只有O(1)，相比与下面要提到的各种快速算法，它的空间占用率是最低的。
没那么暴力解法
在上面的暴力解法中，我们可以看到，它之所以暴力，是因为它的很多计算都是重复的，比如在最内层的循环中求和，前k个元素的和在求前k+1，k+2 ... k+n 个元素的和时又重复计算了一边，这种有重叠子问题的方法，是典型的可以用动态规划(Dynamic programming)的思想来解决的，这个重复计算的过程是可以省略的，前k+1个元素的和就是前k个元素的和再加第k+1个元素就可以了。基于这样的想法，我们可以考虑先构造这样一个数组preSum，它的第i个元素preSum[i]表示输入数组A的前i个元素（0到i-1，不包含i）的和，即
preSum[i] = A[0] + A[1] + ... + A[i-1]这里要格外注意一下数组preSum的起点，我在最初实现的时候，preSum[0]定义成了A[0]，这样看起来似乎是合情合理，但是这样无形之中忽视了A为空的情况，在处理上面的示例1的时候就遇到了问题，这就是边界条件的处理问题，一定要多加小心。最终的实现版本中，我把preSum[0]定义成了0，即表示A是空的情况下（和A中前0个元素的情况下）其和为0。
当我们计算好preSum之后，问题就转化成了满足preSum[x2] - preSum[x1] >= K条件下的最小的x2 - x1。因为此时preSum[x2] - preSum[x1]就表示A中第x1到第x2之间元素的和（其中x1 < x2）。
class Solution {
public int shortestSubarray(int[] A, int K) {
int minLen = A.length + 1;
int[] preSum = new int[A.length + 1];
preSum[0] = 0;
for (int i = 0; i < A.length; i++) {
preSum[i + 1] = preSum[i] + A[i];
}
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length + 1; j++) {
if ((preSum[j] - preSum[i]) >= K) {
if ((j - i) < minLen) {
minLen = j - i;
}
}
}
}
return minLen == A.length + 1 ? -1 : minLen;
}
}相比与暴力解法，这个方法把时间复杂度降到了O(n^2)（代价是空间复杂度升到了O(n)，这也是拿空间换时间，不过这个例子不够典型），看起来已经非常不错了，但是我们能满足吗？不能，好，接下来看时间复杂度O(n)的解法。
优雅的解法
在上面没那么暴力解法中的那个双层循环中，还有一定的优化空间的。
- 比如当
preSum[x2] <= preSum[x1]（其中x1 < x2）时，表明x1到x2之间的元素的和是负数或0，那么就是当preSum[xn] - preSum[x1] >= K则必然有preSum[xn] - preSum[x2] >= K，那么这个时候我们只计算xn - x2即可（x1到x2之间的元素可以全部跳过了，耶！），就不需要计算xn - x1了，因为后者一定是更大的，不满足我们要选最小的条件。 - 另一个角度，当
preSum[x2] - preSum[x1] >= K时，x1就可以跳过了，为什么呢？因为x1到x2已经满足了大于K，再继续从x1开始向后再早，也不会再有比x2距离x1更近的了，毕竟我们要求的是最小的x2 - x1。
以上的两种分析，情况1是把位于末尾没用的x1扔掉，情况2是把指向前面的已经满足条件的x1的指针向后移动1位，这是就需要比较当前最小值与此时刚符合条件的值的大小了。
class Solution {
public int shortestSubarray(int[] A, int K) {
int minLen = A.length + 1;
int[] preSum = new int[A.length + 1];
preSum[0] = 0;
for (int i = 0; i < A.length; i++) {
preSum[i + 1] = preSum[i] + A[i];
}
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < A.length + 1; i++) {
while (!deque.isEmpty() && preSum[i] <= preSum[deque.getLast()]) {
// 1.
deque.pollLast();
}
while (!deque.isEmpty() && preSum[i] - preSum[deque.getFirst()] >= K) {
// 2.
int new_len = i - deque.pollFirst();
if (new_len < minLen) {
minLen = new_len;
}
}
deque.addLast(i);
}
return minLen == A.length + 1 ? -1 : minLen;
}
}其中第二个for循环中，终止条件是i < A.length + 1，因为我们自己构造的数组preSum其长度是A.length + 1。
参考资料
1.https://blog.csdn.net/yanglingwell/article/details/80875790
2.https://www.cnblogs.com/f91og/p/9494922.html
3.https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/solution/
4.https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque