• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> prefixToIndex{{0, -1}};
int prefix = 0;

for (int i = 0; i < nums.size(); ++i) {
prefix += nums[i];
if (k != 0)
prefix %= k;
if (prefixToIndex.count(prefix)) {
if (i - prefixToIndex[prefix] > 1)
return true;
} else {
// only add if absent, because the previous index is better
prefixToIndex[prefix] = i;
}
}

return false;
}
};
``````

## JAVA

``````class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int prefix = 0;
Map<Integer, Integer> prefixToIndex = new HashMap<>();
prefixToIndex.put(0, -1);

for (int i = 0; i < nums.length; ++i) {
prefix += nums[i];
if (k != 0)
prefix %= k;
if (prefixToIndex.containsKey(prefix)) {
if (i - prefixToIndex.get(prefix) > 1)
return true;
} else {
// only add if absent, because the previous index is better
prefixToIndex.put(prefix, i);
}
}

return false;
}
}
``````

## Python

``````class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
prefix = 0
prefixToIndex = {0: -1}

for i, num in enumerate(nums):
prefix += num
if k != 0:
prefix %= k
if prefix in prefixToIndex:
if i - prefixToIndex[prefix] > 1:
return True
else:
prefixToIndex[prefix] = i

return False
``````