Problem description:

/
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 nk 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:
The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Solution:

The main idea is to find whether if there’s two subarray that contains equal remainder.
Let’s say we have a sum of subarray from i...j look like this:
a[i]+a[i+1]+...+a[j]=n1k+q;

If we can find a n, which is greater than j , that qualified for the following equation,
n>j and a[i]+a[i+1]+...+a[j]+...+a[n]=n2k+q;

We can derive a result that the sum of subarray from j...n should be:
a[j+1]+...+a[n]=(n2−n1)k

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        sum_map = {0: -1}
        cur_sum = 0
        for index, num in enumerate(nums):
            cur_sum += num
            if k != 0:
                cur_sum = cur_sum % k
            if cur_sum in sum_map and index - sum_map[cur_sum] > 1:
                return True
            if cur_sum not in sum_map:
                sum_map[cur_sum] = index
        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int sum= 0;
        unordered_map<int, int> map= {{0, -1}};
        
        for(int i= 0; i< nums.size(); i++){
            sum+= nums[i];
            if(k != 0)
                sum = sum%k;
            if(map.count(sum)){
                if(i- map[sum] >1)
                    return true;
            }
            else
                map[sum]= i;
        }
        return false;
    }
};

time complexity: O(n)
space complexity: O(n)

reference:
https://goo.gl/sieyWJ
https://goo.gl/fb8NoY
https://goo.gl/fK1cNG