# 523. Continuous Subarray Sum

## LeetCode [523. Continuous Subarray Sum](https://leetcode-cn.com/problems/continuous-subarray-sum/)

### Description

Given an integer array `nums` and an integer `k`, return `true` *if*`nums` *has a continuous subarray of size **at least two** whose elements sum up to a multiple of* `k` *, or*`false` *otherwise*.

An integer `x` is a multiple of `k` if there exists an integer `n` such that `x = n * k`. `0` is **always** a multiple of `k`.

**Example 1:**

```
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
```

**Example 2:**

```
Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
```

**Example 3:**

```
Input: nums = [23,2,6,4,7], k = 13
Output: false
```

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 109`
* `0 <= sum(nums[i]) <= 231 - 1`
* `1 <= k <= 231 - 1`

### Tags

Math, Dynamic Programming

### Solution

To solve this problem, we can use prefix-sum strategy to check if each subarray whose elements sum up to a multiple of `k`. However, it is an `O(n²)` time complexity operation leading to timeout. We observe that if `preSum[j] - preSum[i] == n * k`, which means the sum of subarray `nums(i,j]` is a multiple of `k`, both `preSum[i]` and `preSum[j]` share the same remainder after mod `k`. Therefore, our goal is changed to find `nums[i]` and `nums[j]` meet the requirements that `nums[i] % k == nums[j] % k` and `j-i ≥ 2`. Obviously, we can achieve this within `O(n)` time complexity by applying a hash table.

### Complexity

* Time complexity: $$O(n)$$
* Space complexity: $$O(\min(n,k))$$

### Code

```go
func checkSubarraySum(nums []int, k int) bool {
	rem2idx, remainder := map[int]int{0: -1}, 0
	for i, num := range nums {
		remainder = (remainder + num) % k
		if preIdx, ok := rem2idx[remainder]; ok {
			if i-preIdx > 1 {
				return true
			}
		} else {
			rem2idx[remainder] = i
		}
	}
	return false
}
```

## Reference

1. [连续的子数组和](https://leetcode-cn.com/problems/continuous-subarray-sum/solution/lian-xu-de-zi-shu-zu-he-by-leetcode-solu-rdzi/)