1590. Make Sum Divisible by P
给一个正整数array nums
请移除长度最短的subarray(可以是空矩阵)
让剩下的元素总和可以被p整除
如果无法达成则回传p
否则回传subarray的长度
思路:
首先我们先计算nums的总和sum
sum % p =remainder
如果remainder == 0，就回传0
不然我们就要去找一段subarray，该subarray % p =remainder
纪录nums[0]+nums[1]+...+nums[i]%p的值(remainder_i)，0 <= i < len(nums)
接着找到j 使nums[j+1]+nums[j+2]...+nums[i] % p ==remainder，0<= j < len(nums)
要怎么找到j
就用一个hash table去纪录每个余数最新出现的index
x = (remainder_i - remainder + p ) % p
去找x在前面有没有出现过
有出现的话
ans = min(ans, i-hash_map[x])
接着更新hash_map里remainder_i的index
就这样一直找完整个矩阵
就可以得到答案
golang code :
func minSubarray(nums []int, p int) int {
sum, res, prev,n := 0, math.MaxInt64, 0,len(nums)
rec := make(map[int]int)
for _, val := range nums {
sum += val
}
remainder := sum % p
if remainder == 0 {
return 0
}
rec[0] = -1
for key, val := range nums {
prev = (prev + val) % p
idx := (prev - remainder + p) % p
if last, ok := rec[idx]; ok {
res = min(res, key-last)
}
rec[prev] = key
}
if res < n {
return res
}
return -1
}