使数组和能被P整除[同余定理+同余定理变形]

前言

同余定理非常经典，采用前缀和 + map，当两个余数前缀和为一个值时，则中间一段子数组刚好对P整除。但是能否找到前面是否有一段子数组和可以对P整除呐？反向思考，找map[P - mod]就知道中间一段子数组和对P取余为mod，前面一段子数组和对P取余为0.

一、使数组和能被P整除

二、同余定理+变形

• 基本思路
  // 前缀和+map，记录前面除p多余的情况a，a属于[0,p)
  // 有一样的余数，不就能整除了嘛，记录余数+位置，同余定理。
• 存在问题
  // 但是可能删除中间部分，并不是以index=0为左边界，还得以当前为右边界不断更新map，变成了O(n²)，就像两层for循环一样了。
  // 但O(n²)显然超时，回到map，可不可以不for循环更新map，直接反向思考，前面为0，那中间那部分余数就算多余的。

func minSubarray(nums []int, p int) int {// 求整个数组和对p的余数sum := getMod(nums,p)// 前缀和记录，可以正向+反向使用前缀和prefix := map[int]int{0:-1}pre,m := 0,len(nums) // 前缀和，最小删除子数组的长度for i,n := range nums {mod := (n + pre) % p // 正向余数x := (p - sum + mod) % p // 反向余数，可得到中间一段子数组和为sum// 正向余数，同余定理，删除最前面的一截。if v,ok := prefix[sum];ok { m = min(m,v + 1)}// 反向余数，以当前位置为需要删除子数组的右边界，寻找符合要求的左边界。if v,ok := prefix[x];ok {m = min(m,i - v)}prefix[mod] = ipre = mod}// 没有寻找到可删除的子数组。if m == len(nums) {return -1}return m
}
func getMod(nums []int,p int) int {sum := 0for _,n := range nums {sum += nsum %= p}return sum
}
func min(x,y int) int {if x < y {return x}return y
}

总结

1）同余定理，可以O(N)复杂度求到子数组和对P整除，基于此多多思考其本质，才能另辟蹊径，做到其变形解法。

参考资料

[1] LeetCode 使数组和能被P整除