1590. 使数组和能被 P 整除

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

func minSubarray(nums []int, p int) int {
	n := len(nums)
	sum := make([]int, n+1)
	for i := 0; i < n; i++ {
		sum[i+1] = (sum[i] + nums[i]) % p
	}
	//sum[n]为数组和模p的结果
	if sum[n] == 0 {
		return 0
	}
	modMap := map[int]int{0: -1}
	ret := len(nums)
	for i := 0; i < n; i++ {
		//寻找[pre,i]=sum[n]，当前[0,i]=sum[i+1]，寻找[0,pre-1]=sum[pre]满足sum[n]=sum[i+1]-sum[pre]
		tar := (sum[i+1] - sum[n] + p) % p
		if pre, ok := modMap[tar]; ok {
			if i-pre < ret {
				ret = i - pre
			}
		}
		modMap[sum[i+1]] = i
	}
	if ret == len(nums) {
		return -1
	}
	
    return ret
}