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.

Analyse

According to the description, we have the formula:

a1 + a2 + a3 + ... + am = n * k

I don’t like the unknow number n, so the formula can be:

a1%k + a2%k + a3%k + ... + am%k = k

Now, all the number in array is smaller than k. The question is equal to:

Given a list of non-negative numbers and a target integer k, all numbers are smaller than k. Write a function to check if the array has a continuous subarray of size at least 2 that sums up to k.

Corner Case

1. if k is 0

since 0 cannot be divide or mod, return false

2. k is a negative number

Math.abs(k) to transform

3. if array containers [0,0]

to make it further, if there is a continuous subarray whose sum is 0, 0 % k === 0 is always true, the function should return true.

Solution

/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var checkSubarraySum = function(nums, k) {
k = Math.abs(k);
for (let i = 0; i < nums.length; i++) {
let sum = nums[i];
for (let j = i + 1; j < nums.length; j++) {
sum += nums[j];
if (sum % k === 0 || (sum === 0 && k === 0)) {
return true;
}
}
}
return false;
};

Where Can We Improve

We used two loops in the previous solution, how to use only one loop?

If there are two different interger A and B, A % k = c andB % k = c, then(A-B) % k = 0 can be inferred.

In this case, if a1 + a2 + a3 + ... + am % k = c and a1 + a2 + a3 % k = c, we can make a conclusion of a4 + a5 + ... + am % k = 0

we can use a Set to record the mod.

AC code

/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var checkSubarraySum = function(nums, k) {
k = Math.abs(k);
let obj = {},
sum = nums;
obj[sum % k] = 1;
for (let i = 1; i < nums.length; i++) {
sum += nums[i];
if (sum % k === 0 || (sum === 0 && k === 0)) {
return true;
}
if (k !== 0 && obj[sum % k]) {
return true;
}
obj[sum % k] = 1;
}
return false;
};