Link
题意
见题链。
思路
自己没想出来。参考灵神题解取思路。自己写出来的。没有用滑动窗口用了前缀和。
代码
package main
func minSizeSubarray(a []int, target int) int {
n := len(a)
var a2 []int
a2 = append(a2, a...)
a2 = append(a2, a...)
prefixSums := make([]int, n*2+1)
for i := 0; i < 2*n; i++ {
prefixSums[i+1] = prefixSums[i] + a2[i]
}
s := prefixSums[n]
if target%s == 0 {
// 注意特判，不然 target%s == 0 的时候会输出-1
return n * (target / s)
}
m := make(map[int]int)
ans := int(2e9)
for i := 0; i < 2*n; i++ {
if idx, ok := m[prefixSums[i+1]-target%s]; ok {
ans = min(ans, i-idx+target/s*n)
}
m[prefixSums[i+1]] = i
}
if ans == int(2e9) {
return -1
}
return ans
}
func min[T ~int | ~int64 | ~string](a, b T) T {
if a < b {
return a
}
return b
}