Solution: Continuous Subarray Sum

Statement

Given an integer array nums and an integer k, determine if nums contains a good subarray. Return true if such a subarray exists; otherwise, return false.

A subarray of nums is considered good if:

• Its length is at least $2$.

• The sum of its elements is a multiple of k.

Notes:

• A subarray is defined as a contiguous sequence of elements within an array.

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

Constraints:

• $1 \leq$ nums.length $\leq 10^4$

• $0 \leq$ nums[i] $\leq 10^5$

• $0 \leq$ sum(nums[i]) $\leq 2^{31} - 1$

• $1 \leq$ k $\leq 2^{31} - 1$

Solution

This algorithm’s essence is identifying a subarray in nums whose sum is a multiple of k. We accomplish this by using cumulative sums and their remainders when divided by k. A hash map helps us quickly check if a particular remainder has been encountered before, allowing us to detect subarrays with the desired property.

Here’s why remainders are essential: when we divide a cumulative sum by k, the remainder reveals the part that isn’t divisible by k. If two cumulative sums yield the same remainder when divided by k, then the difference between these cumulative sums is divisible by k. This indicates that the subarray between these two indices has a sum that’s a multiple of k.

For instance, if we have cumulative sums at indices i and j where $i < j$, and the remainder at index i matches the remainder at index j, then: