Subarray with sum divisible by k

Given an array of random integers, find subarray such that sum of elements in the element is divisible by k.

For example, For A=[2, -3, 5, 4, 3, -1, 7]. The for k = 3 there is a subarray for example {-3, 5, 4}. For, k=5 there is subarray {-3, 5, 4, 3, -1, 7} etc.

We can do some math for this problem.  Let A[i] to A[[j] is such a subarray i.e.

               (A[i]+A[i+1]+...+A[j])%K = 0. Which is equivalent to
           <=> (A[0]+A[1]+....+A[j])%K = (A[0]+A[1]+...A[i])%K

1. So we need to find such a pair of indices (i, j) that they satisfy the above condition.
2. Find Cumulative sum and get mod K of the sum for each position
3. Now, subarray by each pair of positions with same value of cumsum mod k constitute a continuous range whose sum is divisible by K.

The following code is a simple implementation of the above idea. One can modify the code to get all such subarrays instead of printing the first one. This is O(n) time and O(n) space code.

public static int[] SubArraySumModK(final int A[], final int K) {
    int sum = 0;
    final Map<Integer, Integer> candidates = new HashMap<Integer, Integer>();

    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        if (!candidates.containsKey(sum % K)) {
            candidates.put(sum % K, i);
        } else {
            // a subarray found
            return Arrays.copyOfRange(A, candidates.get(sum % K) + 1, i+1);
        }
    }
    return null;
}

Another variation of this problem could be

Given an array of random integers, find max length subarray such that sum of elements in the element is equal a given number.

Similar approach as above. Instead of keeping one index per cumsum (mod k) we now need to maintain a list of indices that have same cumsum. Each pair of these lists is a candidate subarray. So, keep updating the max size among subarrays. Thats is our answer.