Leetcode 523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Analysis:

The naive solution would be for each subarray of the array, check if it's multiple of k. The time complexity would be O(n^2).

To have a O(n) solution, there is a trick to consider. If

a % k == c &&

b % k == c

Then (a - b) % k == 0. 

why? Because a = m * k + c, b = n * k + c, then a - b = (m - n) * k, which modular b is 0.

So based on that observation, we can first do a presum of the array. Then for each number in the presum array, we check if the residual value has already been seen before. If yes and the distance is greater than 1, it means  there must be a subarray of which the sum is multiple of k.

Code (Java):

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (nums == null || nums.length < 2) {
            return false;
        }
        
        int[] preSum = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preSum[i] = nums[i] + preSum[i - 1];
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        
        for (int i = 0; i < preSum.length; i++) {
            
            int res = preSum[i];
            if (k != 0) {
                res = preSum[i] % k;
            }
            if (map.containsKey(res) && (i - map.get(res)) > 1) {
                return true;
            }
            
            if (!map.containsKey(res)) {
                map.put(res, i);
            }
        }
        
        return false;
    }
}