LeetCode: 862. Shortest Subarray with Sum at Least K

题目描述

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [1], K = 1
Output: 1

Example 2:

Input: A = [1,2], K = 4
Output: -1

Example 3:

Input: A = [2,-1,2], K = 3
Output: 3

Note:

1 <= A.length <= 50000
-10 ^ 5 <= A[i] <= 10 ^ 5 1 <= K <= 10 ^ 9

解题思路 —— 滑动窗口

朴素思想(O(n)^2, TLE)

记 ，前 x 数（包括第 x 个数）的和为 frontSum[x]， 则第 i 个数到第 j 个数的和为 frontSum[j]-frontSum[i-1]。
遍历 i, j 的情况，求出和大于等于 K， 且长度最小的数组即可。复杂度 O(n^2)。

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        // 前序和
        vector<long long int> frontSum(A.size()+1, 0);
        for(int i = 1; i <= A.size(); ++i)
        {
            frontSum[i] = frontSum[i-1] + A[i-1];
        }

        int ans = -1;
        // 枚举所有情况
        for(int i = 0; i < A.size(); ++i)
        {
            for(int j = i; j < A.size(); ++j)
            {
                if(frontSum[j+1] - frontSum[i] >= K && (ans == -1 || ans > j+1-i))
                {
                    ans = j+1-i;
                    break;
                }
            }
        }

        return ans;

    }
};

滑动窗口（O(n)）

实际上，当 frontSum[j]-frontSum[i-1] <= 0， 即表示 i 到 j 的元素和小于等于零，会成为后面的负担（增加长度，却不增加和）。因此，j 后面的元素计算最小长度时，可以不用考虑 i 到 j 这一段。具体操作参考代码注释。

AC 代码

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        vector<long long int> frontSum(A.size()+1, 0);

        for(int i = 1; i <= A.size(); ++i)
        {
            frontSum[i] = frontSum[i-1] + A[i-1];
        }

        int ans = -1;

        deque<int> begCandidates; 

        // 每一次循环处理： 以 end 为结束的 Shortest Subarray with Sum at Least K
        for(size_t end = 0; end <= A.size(); ++end)
        {
            // 如果 begCandidates.back() 到 end 的和是负的，
            // 则计算 end 之后的 “以 end 为结束的 Shortest Subarray with Sum at Least K”， 
            // 不再需要从 begCandidates.back() 开头子数组
            while(!begCandidates.empty() && frontSum[end] - frontSum[begCandidates.back()] <= 0)
            {
                begCandidates.pop_back();
            }

            // 如果 begCandidates.front() 到 end 的和大于等于 K， 则其可能是备选方案
            while(!begCandidates.empty() && frontSum[end] - frontSum[begCandidates.front()] >= K)
            {
                // 如果 begCandidates.front() 到 end 的和大于等于 K, 
                // 则后面的计算不再需要 begCandidates.front() 
                // 因为，begCandidates.front()为起始，和大于等于 K 的，
                // 最小距离一定小于等于 end - begCandidates.front()。
                int beg = begCandidates.front();
                begCandidates.pop_front();

                if(ans == -1) ans = end - beg;
                else ans = min(ans, (int)end - beg);
            }

            begCandidates.push_back(end);
        }

        return ans;

    }
};