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
}