974. Subarray Sums Divisible by K

Link

Solution

Two things:

1. HashMap to record partial result

2. for subSum, if we stored them in HashMap with subSum%K form, then we can came out following logic: Assume a array sum[] stored all subSum% K, if we can find a pair <i,j>, which sum[i] == sum[j] Then: A[i] + A[i+1] + .... A[j] = sum[j] - sum[i] + n*K = 0 + n*k (which means could be divided by K)

 public int subarraysDivByK(int[] A, int K) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        int current = 0, ret = 0, min = 0;
        for(int i = 0; i < A.length; i++){
            current = ( current + A[i] )% K;
            if(current < 0) current += K; //補正
            
            // assume : sum[] put all subsum%K
            // then sum[i] == sum[j] 
            //then A[i] + A[i+1] + ... A[j] shall be K * n 
            ret += map.getOrDefault(current, 0);
            map.compute(current, (k, v) -> {
                if(!map.containsKey(k)){
                    return 1;
                }
                return v+1;
            });
        }
        return ret;
    }