[LeetCode] Continuous Subarray Sum

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 a multiple of k, that is, sums up to n*k where n is also an integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if(!k) {
for(int i = 1; i < nums.size(); i++)
if(!nums[i] && nums[i] == nums[i - 1])
return true;
} else {
unordered_map<int, int> countOfNums;
long lNum = (nums[0] %= k);
countOfNums[lNum]++;
for (int i = 1; i < nums.size(); i++) {
nums[i] %= k;
lNum = (lNum + nums[i]) % k;
if(!lNum || (nums[i] == nums[i - 1] && !nums[i]))
return true;
if(nums[i]) {
countOfNums[lNum]++;
if (countOfNums[lNum] >= 2)
return true;
}
}
}
return false;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/01/18/PS/LeetCode/continuous-subarray-sum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.