LeetCode：862. Shortest Subarray with Sum at Least K - Python

问题描述：

和至少为 K 的最短子数组

返回 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

问题分析：

随着做题的深入，越发的感觉智商不够用，用暴力的方法很显然时间复杂度为O(n2)。这个题目主要是参考了官方的给解答，给出答案时间复杂度为O(n),空间复杂度也为O(n)，现在自己进行解读和总结。 （1）题目提示3，已经表明 k >= 1 的，也就是说 k>0 ，后面会用到。 （2）设，dp[i] = A[0]+A[1]+...+A[i-1]，就是 dp[i] = 列表第i个元素之前的和，这时，你可以联想到，这个列表的所有连续子序列的和都可以由这个dp[i]推导出。例如  A[3]+...+A[5] = dp[6] - dp[3] 。 （3）从（2）可以发现，连续子序列的值就是 dp 后一个值减去前一个值，而且是必须大于0才是有效的，因为（1）已经说明了 k 是必须大于 0 的。 （4）其次是不能忽略的一个点是，要求的是 最短 子序列和的不小于 k 。 （5）解题思路，扫描一遍dp数组，并 依次添加到 一个 队列 里面（添加的是位置索引 i，在后面的计算过程，可以直接通过位置索引，找到对应的 dp[i] ，也方便后面求最短距离或者最短长度）。 （6）然后对整个队列扫描，看看队列里面有那些 位置 对应的 dp值，是大于 dp[i] 的，并把它们删除，（3）已经说明。 （7）然后更新最优解 res，在更新的过程中，也伴随着出队操作，出队操作会不会影响后续的子序列？可以这样理解，因为要求的是符合题目的 最短子序列 的 长度 。这个可以反证法证明。 （8）直至遍历结束，总结，官方给出的时间复杂度和空间复杂度都为 O(n) ，虽然 for 循序下面也有一个循环 while，应该是那个遍历的情况远小于 n 可以忽略不计。这个题目也可以用二分法或者动规来做，时间复杂度应该都比这个方法高。

Python3实现：

import collections class Solution(object): def shortestSubarray(self, A, K): n, dp = len(A), [0] # 初始化dp[i] = A[0]+A[1]+...+A[i-1] for v in A: dp.append(dp[-1] + v) queue, res = collections.deque(), n + 1 # 初始化队列、结果变量 for i in range(n+1): while queue and dp[i] <= dp[queue[-1]]: queue.pop() # 出队, 删除不符合的 while queue and dp[i] - dp[queue[0]] >= K: res = min(res, i - queue.popleft()) # 从左边出队，并更新最短距离。 queue.append(i) # 入队 return res if res < n + 1 else -1 #返回最优解 if __name__ == '__main__': solu = Solution() A, K = [2, -1, 2], 3 print(solu.shortestSubarray(A, K))

欢迎讨论哦

参考链接： [1] https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/solution/