NeetCode #124LC-523MediumArrays & Hashing
← Back to All Problems#124 · #523 · Continuous Subarray Sum(连续的子数组和)
📌 Problem Statement & Constraints
Given an integer array
nums and an integer k, return true if nums has a good subarray: a contiguous subarray of length at least 2 whose sum is a multiple of k. Constraints: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 10^9, 1 <= k <= 2^31 - 1.💡 Core Algorithmic Approaches
- As with all divisible-subarray problems, the key is prefix sums modulo
k: two prefixes with the same residue bound a subarray whose sum is divisible byk. - Because the subarray must have length at least 2, store the earliest index at which each residue appeared and require the gap to be at least 2.
- Seed the map with
{0: -1}so that a prefix at index 1 can pair with the virtual empty prefix at index -1, giving length 2. - Only the first occurrence of each residue needs to be stored, since it maximises the gap.
💻 Benchmark Python3 Implementation
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
first = {0: -1} # residue -> earliest prefix index
cur = 0
for i, x in enumerate(nums):
cur = (cur + x) % k
if cur in first:
if i - first[cur] >= 2: # length at least 2
return True
else:
first[cur] = i # keep only the earliest
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass with O(1) average hash operations.
💾 Space Complexity
O(min(n, k)) for the residue map.
⚠️ Interview Pitfalls & Follow-ups
- Seeding with
{0: 0}instead of{0: -1}: the virtual empty prefix sits at index -1, and using 0 would make a single-element subarray satisfy the length check. - Overwriting
first[cur]: the earliest index must be preserved to maximise the gap. - Requiring
>= 2on the element count rather than the index gap: the gapi - first[cur]already equals the subarray length. - Forgetting the
k = 1case: every sum is divisible by 1, so any array of length at least 2 returnstrue; the algorithm handles it without a special case.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.