Arrays and Hashing Prefix sums
80. Continuous Subarray Sum
You are given an array of integers nums and a positive integer k. Return true if some subarray of at
least two elements has a sum that is a multiple of k, and false otherwise.
A subarray is a contiguous sequence of elements from nums. A sum is a multiple of k when it equals
k times some integer: 0, k, -k, 2k and so on.
Example 1
Input: nums = [4, -1, 6, 3, 2], k = 7
trueExplanation: The whole array adds up to 14, which is 7 × 2. No shorter subarray of two or more elements adds up to a multiple of 7.
Example 2
Input: nums = [5, 1, 10, 3], k = 5
falseExplanation: [5] and [10] are multiples of 5, but each is a single element. The longer subarrays add up to 6, 11,
13, 16, 14 and 19, and none of those is a multiple of 5.
Example 3
Input: nums = [8, -5, -3], k = 1000
trueExplanation: The whole array adds up to 0, and 0 is a multiple of every k, because 0 = 1000 × 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 1091 ≤ k ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.