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.

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[0];
    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;
};