⚡Flashcard Drill➔
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

  1. 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 by k.
  2. 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.
  3. 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.
  4. 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 >= 2 on the element count rather than the index gap: the gap i - first[cur] already equals the subarray length.
  • Forgetting the k = 1 case: every sum is divisible by 1, so any array of length at least 2 returns true; 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems