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]即可
class Solution {
public int minSubarray(int[] nums, int p) {
long sum = 0;
for(int n : nums){
sum += n ;
}
if(sum % p == 0)
return 0;
if(sum < p)
return -1;
int t = (int) (sum % p);
int res = nums.length;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int[] pre = new int[nums.length + 1];
for(int i = 1; i < nums.length + 1; i++) {
pre[i] = (pre[i-1]%p + nums[i - 1]%p)%p;
}
for(int i = 0; i <= nums.length; i++) {
int y = (int) (pre[i] % p);
if(map.containsKey((y - t + p)%p))
res = Math.min(res, i - map.get((y - t + p)%p));
map.put(y, i);
}
if(res == nums.length)
return -1;
return res;
}
}