523. Continuous Subarray Sum

Problem

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

Problem Summary

Given an integer array nums and an integer k, write a function to determine whether the array contains a continuous subarray that satisfies both of the following conditions:

• The subarray size is at least 2, and
• The sum of the subarray elements is a multiple of k.

If it exists, return true; otherwise, return false. If there exists an integer n such that the integer x satisfies x = n * k, then x is called a multiple of k.

Solution Approach

• Easy problem. The problem only asks whether one exists; it does not require finding all solutions. Use a variable sum to record the cumulative sum. The sum of a subarray can be obtained by subtracting prefix sums. For example, the sum of elements in the interval [i,j] can be obtained from prefixSum[j] - prefixSum[i]. When prefixSums[j]−prefixSums[i] is a multiple of k, prefixSums[i] and prefixSums[j] have the same remainder when divided by k. Therefore, we only need to compute the remainder of the prefix sum at each index divided by k, and use a map to store the first index where each remainder appears. If the same remainder key exists in the map, it means the current index and the index recorded by this key in the map can satisfy the condition that the total sum is a multiple of k. Then just check whether the condition that the size is at least 2 can be satisfied. Subtract the two indices; if the length is greater than or equal to 2, the condition is satisfied and true can be returned.

Code

package leetcode

func checkSubarraySum(nums []int, k int) bool {
	m := make(map[int]int)
	m[0] = -1
	sum := 0
	for i, n := range nums {
		sum += n
		if r, ok := m[sum%k]; ok {
			if i-2 >= r {
				return true
			}
		} else {
			m[sum%k] = i
		}
	}
	return false
}