# Continuous Subarray Sum Problem

## Description

LeetCode Problem 523. Given an array of non-negative integers **nums** and an integer **k**, check if the array has a continuous subarray of size at least 2 that sums up to a multiple of **k**.

Example:

1
2
3

Input: nums = [23, 2, 4, 6, 7], k = 6
Output: True
Explanation: [2, 4] is a continuous subarray of size 2 and sums up to 6.

## Solution

This problem is similar to the `subarray sum divisible by k problem`

.

#### Brute Force Approach

A simple solution is to use the `brute force`

approach. We can consider all possible subarrays and check whether the sum of each subarrays is divisible by *k*.

We can use a left pointer *l* and a right pointer *r* to enumerate all possible subarrays. We loop through each integer in the array *nums* with *l*. For each *l*, we iterate with *r* from *l*+1 to the end of the array. In the meantime, we use a *sum* variable to record the accumulative sum from *l* to *r*. If *sum* is divisible by *k* and the distance between *l* and *r* is greater than 1, we return true; otherwise, we keep on searching. If we cannot find one such subarray, we return false.

The time complexity of this approach is O(n^{2}),
and the space complexity is O(1).

#### Hash Table Approach

The time complexity can be further reduced if we use a `hash table`

to store intermediate results. The solution is similar to the solution to the `subarray sum divisible by k problem`

. The only difference is that instead of storing the (modulo, count) pair in the hash table, we store the (modulo, index) pair, because we only need to find out whether such a subarray exists, but not how many such subarrays.

We loop through the array and use an *accu_sum* variable to store the accumulative sum. During the iteration, we calculate the modulo (*accu_sum* % *k*). We then store the modulo to a hash table as a key and the index of the current element as the value.

During the iteration, if we have already found an *accu_sum* that has the same modulo with *k* as the current *accu_sum*, then the subarray between these two *accu_sum* has a sum divisible by *k*.

We can check the distance between the index of the current element and the index of the previous element to see whether the size of the subarray is at least two. If so, we can return true. Otherwise, we keep on searching.

The time complexity can be reduced to O(n), and the space complexity is O(k).

## Sample C++ Code

This is a C++ implementation of the hash table approach.

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
27
28
29
30
31
32
33
34
35

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <climits>
using namespace std;
bool checkSubarraySum(vector<int>& nums, int k) {
int len = nums.size();
if (len < 2)
return false;
unordered_map<int, int> ht;
int accu_sum = 0;
ht[0] = -1;
if (k == 0) k = INT_MAX;
for (int i = 0; i < len; i ++) {
accu_sum += nums[i];
if (ht.find(accu_sum % k) != ht.end()) {
if (i - ht[accu_sum % k] > 1)
return true;
} else {
ht[accu_sum % k] = i;
}
}
return false;
}
int main() {
vector<int> nums={23, 2, 4, 6, 7};
int k = 6;
cout << checkSubarraySum(nums, k) << endl;
}