# 974. Subarray Sums Divisible by K

[Link](https://leetcode.com/problems/subarray-sums-divisible-by-k/)

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