396. Continuous Subarray Sum
You are given an array nums of non-negative integers and a positive integer k.
Return true if nums contains a contiguous subarray of length at least 2 whose elements sum to a multiple of k, and false otherwise.
Note that 0 counts as a multiple of every k, and that a single element divisible by k does not qualify — the subarray must span at least two positions.
Example 1:
Input: nums = [5, 3, 7, 2], k = 12
Output: true
Explanation: The subarray [3, 7, 2] sums to 12, which is a multiple of 12 and spans three positions.
Example 2:
Input: nums = [1, 2, 12], k = 6
Output: false
Explanation: The length-2+ subarrays sum to 3, 14 and 15 — none is a multiple of 6. The lone 12 is divisible by 6 but has length 1, so it does not count.
Example 3:
Input: nums = [0, 0], k = 9
Output: true
Explanation: [0, 0] sums to 0, and 0 is a multiple of every k.
Constraints:
- 1 ≤ nums.length ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁹
- 1 ≤ k ≤ 2³¹ - 1
Hints:
Think in prefix sums. If P[i] is the sum of the first i elements, the subarray between two prefixes sums to P[i] - P[j] — and that difference is a multiple of k exactly when P[i] and P[j] leave the same remainder mod k.
Scan once, hashing each remainder to the **earliest** prefix index where it appeared, seeded with {0: -1}. At index i, if the current remainder was first seen at index j and i - j >= 2, the subarray nums[j+1..i] has length >= 2 and a sum divisible by k.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [5, 3, 7, 2], k = 12
Expected output: true