题目:
思想:
‘≡’同余
例如 nums=[11,2,5,7,8,9],p=10,那么把 [5,7] 去掉,剩余的数字相加等于 30,可以被 p 整除。
所有元素和为 $42mod10 = 2$
设所有元素和为x,去掉的元素和为y,使得x-y 能被p整除,满足
y≡x(mod p)->x % p = y % p
通过前缀和,问题转换成:在前缀和数组上找到两个数 s[left]
和 s[right]
,满足 right−left 最小且
$$
s[right] - s[left] ≡ x (mod p)
->s[right] - x ≡ s[left] (mod p)
$$
((s[right]-x)modp+p) mod p = s[left] mod p
遍历 sss 的同时,用哈希表 last\textit{last}last 记录 s[i]mod p 最近一次出现的下标,如果 lastlast 中包含
(s[i] mod p−x mod p+p) mod p,设其对应的下标为 j,那么 [j,i) 是一个符合题目要求的子数组。
枚举所有 i,计算符合要求的子数组长度的最小值,就是答案。如果没有符合要求的子数组,则返回 −1。
代码实现时,可以把答案初始化成 nums 的长度 n。如果最后答案等于 n,则表示没有符合要求的子数组,因为题目不允许将整个数组都移除。
last是一个map,键是整数,值是整数。j, ok := last[(v-x+p)%p]这一行代码是在last中查找键为(v-x+p)%p的元素,并将其值赋给变量j。如果这个键不存在,那么ok的值将会是false,否则ok的值将会是true。
这个语法的返回值是两个值,第一个值是键所对应的值,第二个值是一个布尔值,表示该键是否存在。
如果ok的值是true,那么代码中的if语句将会执行,它将ans的值更新为i-j和ans中的最小值。如果ok的值是false,那么if语句将会被跳过,程序将会继续执行下去。
代码:
1 | class Solution: |
1 | package main |