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
}