Continuous Subarray Sum
Problem
Return true if the array has a contiguous subarray of length at least 2 whose sum is a multiple of k (0 counts as a multiple).
Example 1
Input: nums = [23, 2, 4, 6, 7], k = 6 Output: true
[2, 4] sums to 6.
Example 2
Input: nums = [23, 2, 6, 4, 7], k = 13 Output: false
Test cases
Case 1
Input: [23,2,4,6,7], 6 Expected: true
Case 2
Input: [23,2,6,4,7], 13 Expected: false
Case 3
Input: [23,2,6,4,7], 6 Expected: true
Case 4
Input: [5,0,0], 3 Expected: true
View solutionHide solution1 approach
1. Prefix remainders
Time O(n)Space O(min(n, k))
Two prefixes with the same remainder mod k bound a subarray whose sum is a multiple of k. Store the first index of each remainder; require length ≥ 2.
function checkSubarraySum(nums, k) { const first = new Map([[0, -1]]); // remainder -> earliest index let sum = 0; for (let i = 0; i < nums.length; i++) { sum = (sum + nums[i]) % k; if (first.has(sum)) { if (i - first.get(sum) >= 2) return true; } else first.set(sum, i); } return false;}