0862_和至少为 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
Note:
1. 1 <= A.length <= 50000
2. -10 ^ 5 <= A[i] <= 10 ^ 5
3. 1 <= K <= 10 ^ 9
暴力算法
func shortestSubarray(A []int, K int) int {
minLen := 50001
tail := len(A) – 1
for i := 0; i <= tail; i++ {
sum := A[i]
if sum >= K {
minLen = 1
break
}
for j := i + 1; j <= tail; j++ {
sum += A[j]
if sum >= K {
l := j – i + 1
if l < minLen {
minLen = l
}
break
}
}
}
if minLen != 50001 {
return minLen
}
return -1
}
高性能版本算法
func shortestSubarray(A []int, K int) int {
size := len(A)
sums := make([]int, size+1)
for i, n := range A {
if n >= K {
return 1
}
sums[i+1] = sums[i] + n
}
res := size + 1
// 存储 0 —-i, 有可能是符合条件的最短子串的 head
deque := make([]int, 0, 0)
for i := 0; i < size+1; i++ {
for len(deque) > 0 && (sums[i]-sums[deque[0]] >= K) {
// i 递增
// 可能有 j>i 使得 sums[j] – sums[deque[0]] >= K
// 但是由于 j>i, 所以 deque[0]—i 是以 deque[0] 作为头的最短的符合条件的子串
// 把 deque[0] 删除
res = min(res, i-deque[0])
deque = deque[1:]
}
for len(deque) > 0 && (sums[i] <= sums[deque[len(deque)-1]]) {
// 如果存在 j>i>deque[r] 使得 sums[j] – sums[deque[r]] >= K
// 由于 sums[deque[r]] >= sums[i] 则
// sums[j] – sums[i] >= K 一定成立，并且 j-i < j-deque[r]
// 所以，以 deque[r] 作为头, 不可能是最短的符合条件子串, 删除
deque = deque[:len(deque)-1]
}
deque = append(deque, i)
}
if res == size+1 {
return -1
}
return res
}
个人思路
相对于暴力破解, 重复计算两个元素之间的和, 所以此处必须进行优化, 只需要循环一遍数组, 存储 0 - i 元素的和
假如 a <b,sums[b]-sums[a]>=K,b- a 则是子串长度
deque(双端队列) 存储 0 -i, 可能符合条件的最短子串的 head
遍历 sums, 取 deque 的 [0], 判断该元素作为子串的 head, 是否符合条件, 如果符合条件, 那么它将是该数组元素作为 head 的符合条件的子串中, 最短的子串, 从 deque 中剔除 [0], 减少后面的 sums 比次数
取 deque 的尾, 值为 r,sums[r]>=sums[i], 那么如果后面存在 sums[j]-sums[r]>=k, 那么 j >i>r,i->j 之间的子串肯定也符合条件, 并且更短, 已 r 为 head 的子串, 不可能是最短的字段, 在这里可以删除 deque 的这个尾, 减少比对次数
总结
在 leetcode 社区中, 有 Java 版本的算法代码, 思路和此处思路完全一致, 但是时间效率比 Golang 版的搞,Golang 版 170ms 左右,Java 版本 40+ms
笔者经过对比代码, 主要区别在于 deque 这个存储容器, 在 JDK 中有对应的数据结构 Deque 双端队列, 数据结构的插入效率导致的, 笔者猜测 Java 中该结构用的双向链表实现的, 在插入元素过程中, 不需要扩容, 内存分配效率很高
Golang 版本代码,deque 用的 slice 切片, 在 append 过程中, 不断的扩容, 进行内存分配, 导致效率低
有兴趣的朋友可以在此处优化 deque 这个数据结构, 采用 struct 对象, 构建双向链表结构, 相信, 效率和 Java 版本的应该差不多, 在此, 篇幅限制, 双向链表也不是该算法的核心, 笔者就到此为止
数据结构作为数据的存储容易, 对算法的影响也是巨大的
GitHub
项目源码在这里
笔者会一直维护该项目, 对 leetcode 中的算法题进行解决, 并写下自己的思路和见解, 致力于人人都能看懂的算法
个人公众号
喜欢的朋友可以关注, 谢谢支持
记录 90 后码农的学习与生活