README ¶
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
题目大意
返回 A 的最短的非空连续子数组的长度,该子数组的和至少为 K 。如果没有和至少为 K 的非空子数组,返回 -1 。
提示:
- 1 <= A.length <= 50000
- -10 ^ 5 <= A[i] <= 10 ^ 5
- 1 <= K <= 10 ^ 9
解题思路
- 给出一个数组,要求找出一个最短的,非空的,连续的子序列且累加和至少为 k 。
- 由于给的数组里面可能存在负数,所以子数组的累加和不会随着数组的长度增加而增加。题目中要求区间和,理所应当需要利用
prefixSum
前缀和,先计算出prefixSum
前缀和。 - 简化一下题目的要求,即能否找到
prefixSum[y] - prefixSum[x] ≥ K
,且y - x
的差值最小。如果固定的y
,那么对于x
,x
越大,y - x
的差值就越小(因为x
越逼近y
)。所以想求区间[x, y]
的最短距离,需要保证y
尽量小,x
尽量大,这样[x, y]
区间距离最小。那么有以下 2 点“常识”一定成立:- 如果
x1 < x2
,并且prefixSum[x2] ≤ prefixSum[x1]
,说明结果一定不会取x1
。因为如果prefixSum[x1] ≤ prefixSum[y] - k
,那么prefixSum[x2] ≤ prefixSum[x1] ≤ prefixSum[y] - k
,x2
也能满足题意,并且x2
比x1
更加接近y
,最优解一定优先考虑x2
。 - 在确定了
x
以后,以后就不用再考虑x
了,因为如果y2 > y1
,且y2
的时候取x
还是一样的,那么算距离的话,y2 - x
显然大于y1 - x
,这样的话肯定不会是最短的距离。
- 如果
- 从上面这两个常识来看,可以用双端队列
deque
来处理prefixSum
。deque
中存储的是递增的x
下标,为了满足常识一。从双端队列的开头开始遍历,假如区间和之差大于等于K
,就移除队首元素并更新结果res
。队首移除元素,直到不满足prefixSum[i]-prefixSum[deque[0]] >= K
这一不等式,是为了满足常识二。之后的循环是此题的精髓,从双端队列的末尾开始往前遍历,假如当前区间和prefixSum[i]
小于等于队列末尾的区间和,则移除队列末尾元素。为什么这样处理呢?因为若数组都是正数,那么长度越长,区间和一定越大,则prefixSum[i]
一定大于所有双端队列中的区间和,但由于可能存在负数,从而使得长度变长,区间总和反而减少了,之前的区间和之差值都没有大于等于K
(< K),现在的更不可能大于等于K
,这个结束位置可以直接淘汰,不用进行计算。循环结束后将当前位置加入双端队列即可。遇到新下标在队尾移除若干元素,这一行为,也是为了满足常识一。 - 由于所有下标都只进队列一次,也最多 pop 出去一次,所以时间复杂度 O(n),空间复杂度 O(n)。
代码
func shortestSubarray(A []int, K int) int {
res, prefixSum := len(A)+1, make([]int, len(A)+1)
for i := 0; i < len(A); i++ {
prefixSum[i+1] = prefixSum[i] + A[i]
}
// deque 中保存递增的 prefixSum 下标
deque := []int{}
for i := range prefixSum {
// 下面这个循环希望能找到 [deque[0], i] 区间内累加和 >= K,如果找到了就更新答案
for len(deque) > 0 && prefixSum[i]-prefixSum[deque[0]] >= K {
length := i - deque[0]
if res > length {
res = length
}
// 找到第一个 deque[0] 能满足条件以后,就移除它,因为它是最短长度的子序列了
deque = deque[1:]
}
// 下面这个循环希望能保证 prefixSum[deque[i]] 递增
for len(deque) > 0 && prefixSum[i] <= prefixSum[deque[len(deque)-1]] {
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
}
if res <= len(A) {
return res
}
return -1
}
Documentation ¶
There is no documentation for this package.
Click to show internal directories.
Click to hide internal directories.