难题本 | LeetCode862. 和至少为 K 的最短子数组

题目链接：https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/

这题的思路真是弯弯绕绕，看了很多份题解，最后还是我BUPT学长的一通模拟让我悟道了[1]。

分析：

题目要求返回数组A的最短的非空连续子数组的长度，该子数组的和至少为K。

最开始想到的是暴力。假设数组长度为n，我们分别求出长度为1、2、…、n的子数组的最大和，将他们按顺序和K比较，第一个比K大的长度就是答案。这样的做法时间复杂度是O(n2)，有点复杂。

之后就没有想法了。跟泓泓挣扎了半天，还是只能去看题解。

不得不说，官方题解真是不讲人话[2]，不到40行代码的思路，硬是能被说成鬼都看不懂的样子。

首先，为了方便求任意一段连续子数组的和，我们需要使用前缀和数组prefix_sum。在这个题目中，prefix_sum[i]表示的是从A[0]到A[i - 1]的前缀和，注意是A[i - 1]，作用后面会讲。总之，求前缀和的办法是很常规的。

我们知道，求得了前缀和数组之后，对于两个下标x、y（设y>x），prefix_sum[y] - prefix_sum[x]表示的就是从A[x + 1]到A[y]这段子数组的和。那么，问题就转化为了针对prefix_sum数组，求一对x和y，满足prefix_sum[y] - prefix_sum[x] >= K，且y - x最小。

朴素的思想是遍历每一对y和x，这样的复杂度还是O(n2)，显然需要用某种更巧妙的办法让我们摆脱两重循环。

于是引出官方题解中的第一条性质：

对于prefix_sum数组，假设有下标**a > b**，且prefix_sum[a] <= prefix_sum[b]，那么对于它们后面的某个下标y来说，只需要考虑a ~ y这一段是否满足条件，而不再需要考虑b ~ y这一段了。这是因为，prefix_sum[y] - prefix_sum[a] >= prefix_sum[y] - prefix_sum[b]，而且y - a < y - b，如果b ~ y这一段能满足条件，那么a ~ y这一段也一定能满足条件，而且这段子数组的长度更小。

如果我没有讲清楚，不妨看看参考[1]中的模拟大法：

本条性质的模拟

我们使用一个双端队列deque来利用这个性质。让下标从前往后走，保持deque中保存的下标x0、x1、…始终满足prefix_sum[x0] < prefix_sum[x1] < ...；注意，由于下标是从前往后走的，当出现了某个prefix_sum[x_m] < prefix_sum[deque.back()]的时候，说明对于之后的下标y来说，x_m是更为合适的选择，也因此可以直接将队尾的元素剔除。

使用下面的代码来进行实现，注意deque的初始元素0。
// deque<int> monoq;			// 变量名与官方题解保持一致
monoq.push_back(0);    		 	// 放入一个0
for (i = 1; i <= A.size(); ++i)  // 下标从前往后走 
{
    while (!monoq.empty() && prefix_sum[monoq.back()] >= prefix_sum[i])
    {
        monoq.pop_back();  // 当前这个i满足性质一，使得后续的y只需要考虑下标i
    }
    ...
}
实现了性质一，需要引出性质二：

对于一个固定的下标x来说，第一次遇见某个y满足prefix_sum[y] - prefix_sum[x] >= K之后，其后更大的下标y_bigger就不必再考虑x了。这很合乎直觉，因为我们要求的是最小的y - x。

我们的下标从前往后走的时候，当前下标既是x，也是y。更确切地说，设当前下标为i，它向前需要看能否满足prefix_sum[i] - prefix_sum[x] >= K；向后需要考虑自己作为区间起点的情况，也就是作为一个x，淘汰掉队列中现有的满足性质一的那些元素。

上面的代码已经成功利用了性质一，现在只需要再从队首去找满足性质二的元素即可：
for (i = 1; i <= A.size(); ++i)
{
    /* 性质一、当前下标作为区间起点的情况 */
    while (!monoq.empty() && prefix_sum[monoq.back()] >= prefix_sum[i])
    {
        monoq.pop_back();
    }
    /* 性质二、当前下标作为区间终点的情况 */
    while (!monoq.empty() && prefix_sum[i] - prefix_sum[monoq.front()] >= K)
    {
        ans = min(ans, i - monoq.front());
        monoq.pop_front();
    }
    /* 当前下标放入队列中，作为区间起点 */
    monoq.push_back(i);
}

AC代码：

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int prefix_sum[50010];  // 前缀和数组
        deque<int> monoq;       // 单调队列
        int i;                  // 循环变量
        int ans = A.size() + 1; // 最终答案，初始值大于数组长度，是个违法数值

        /* 循环一遍求得前缀和 */
        prefix_sum[0] = 0;      // !IMPORTANT
        for (i = 1; i <= A.size(); ++i)  // prefix_sum[i]为A[0]到A[i - 1]的前缀和
        {
            prefix_sum[i] = prefix_sum[i - 1] + A[i - 1];
        }

        /* 再循环一遍求得最短子数组的长度 */
        monoq.push_back(0);     // 放入一个0
        for (i = 1; i <= A.size(); ++i)
        {
            /* 性质一、当前下标作为区间起点的情况 */
            while (!monoq.empty() && prefix_sum[monoq.back()] >= prefix_sum[i])
            {
                monoq.pop_back();
            }
            /* 性质二、当前下标作为区间终点的情况 */
            while (!monoq.empty() && prefix_sum[i] - prefix_sum[monoq.front()] >= K)
            {
                ans = min(ans, i - monoq.front());
                monoq.pop_front();
            }
            /* 当前下标放入队列中，作为区间起点 */
            monoq.push_back(i);
        }

        return ans == A.size() + 1 ? -1 : ans;
    }
};

一些细节

在之前的分析中我们提到过，在这个题目中，prefix_sum[i]表示的是从A[0]到A[i - 1]的前缀和。这里的前缀和数组的表示方法主要是为了满足区间长度为A.size()时的情况。我们的monoq需要有个初始元素0，这使得prefix_sum[0]也受到考虑。当答案区间长度为A.size()的时候，如样例3：
输入：A = [2,-1,2], K = 3
输出：3
如果没有一个prefix_sum[monoq.front()] == 0，前缀和prefix_sum[3]会直接减掉prefix_sum[1]，造成输出为-1。

参考文章

[1] 王琛.Leetcode 862 Shortest Subarray with Sum at Least K[EB/OL].2018-07-02

https://buptwc.github.io/2018/07/02/Leetcode-862-Shortest-Subarray-with-Sum-at-Least-K/

[2] LeetCode.和至少为 K 的最短子数组[EB/OL].2019-08-13

https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/solution/he-zhi-shao-wei-k-de-zui-duan-zi-shu-zu-by-leetcod/