Categories
interview

Continous Subarray Sum

/**
@param {number[]} nums
@param {number} k
@return {boolean}
*/
const checkSubarraySum = (nums, k) => {
  const map = { 0: -1};
  let sum = 0;
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]; 
    if (k != 0)
      sum %= k;
    if (map[sum] >= -1) {
      if (i - map[sum] > 1)
        return true;
    } else
      map[sum] = i;
  }
  return false;
};
// Time Complexity O(n)
// Space Complexity O(n)

console.log(checkSubarraySum([23, 2, 4, 6, 7], 6));
// Output: true

/**
@param {number[]} nums
@param {number} k
@return {boolean}
*/
const checkSubarraySumBruteForce = (nums, k) => {
  for (var start = 0; start < nums.length - 1; start++) {
    var sum = nums[start];
    for (var end = start + 1; end < nums.length; end++) {
      sum += nums[end];
      if (sum === k || (k !== 0 && sum % k === 0))
        return true;
    }
  }
  return false;
};
// Time Complexity O(n2)
// Space Complexity O(1)

console.log(checkSubarraySumBruteForce([23, 2, 4, 6, 7], 6));
// Output: true

Demo