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;
    }
    
}