Continuous Subarray Sum
Prefix Sum:
This is a running total of the elements from the start of the array up to the current element. The use of prefix sums allows us to compute the sum of any subarray nums [i-j] as prefixSum[j]−prefixSum[i−1].
Modulo Operation:
If the difference between two prefix sums prefixSum[j] and prefixSum[i−1] is a multiple of k, then their modulo k results will be identical. Mathematically, (prefixSum[j]−prefixSum[i−1])%k==0 simplifies to prefixSum[j]%k==prefixSum[i−1]%k.
1/**
2 * @param {number[]} nums
3 * @param {number} k
4 * @return {boolean}
5 */
6var checkSubarraySum = function(nums, k) {
7 const prefixSumMod = new Map();
8 let prefixSum = 0;
9 prefixSumMod.set(0,-1);
10 for (let i = 0; i < nums.length; i++){
11 prefixSum += nums[i];
12 let mod = prefixSum % k;
13
14 if(mod < 0) mod += k;
15
16 if(prefixSumMod.has(mod)){
17 if(i - prefixSumMod.get(mod) > 1 ){
18 return true;
19 }
20 }else{
21 prefixSumMod.set(mod,i);
22 }
23 }
24 return false;
25};
26
27console.log(checkSubarraySum([23,2,4,6,7],6))