Make Sum Divisible by P

给一个数组nums和一个p, 求删去最小的子数组后的数字和可以整除p.

let s = sum of nums, r = s mod p -> r = (s + p) mod p

因为我们知道presum可以用两个指针表示其中间隔的和. let (i, j) = indexs in presum where 0 <=i <= j <= presum.length.

since r = (s + p) mod p, then r = (pre[j] – pre[i] + p) mod p

因为我们知道2sum中, 两个index可以用O(n)的space换取O(n^2) -> O(n)的时间.

since r = (pre[j] – pre[i] + p) mod p, then pre[i] =(pre[j] – r + p) % p;

所以我们用map存pre[i]即可