What is the main pattern for solving Continuous Subarray Sum?

Use prefix sums and track modulo k values in a hash map to detect subarrays summing to multiples of k.

Can this problem handle large arrays efficiently?

Yes, the O(n) prefix sum with hash map ensures efficient handling up to the constraint of 10^5 elements.

Why do we store 0:-1 in the hash map?

To account for subarrays starting at index 0, ensuring correct detection of valid sums from the beginning.

How do we avoid single-element false positives?

Always check that the subarray length is at least 2 when a modulo repeats in the hash map.

What if k is negative or zero?

Handle k carefully: negative k works with modulo as usual, but k=0 requires checking subarray sums directly without modulo.

#523

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

连续的子数组和

给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个好的子数组返回 true ，否则返回 false ：一个好的子数组是：长度至少为 2 ，且子数组元素总和为 k 的倍数。注意：子数组是数组中连续的部分。如果存在一个整数 n ，令整数 x 符合 x = …

数组哈希表数学前缀和

题目描述

给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：

一个 好的子数组 是：

长度 至少为 2 ，且
子数组元素总和为 k 的倍数。

注意：

子数组 是数组中连续的部分。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

lightbulb

解题思路

方法一：前缀和 + 哈希表

根据题目描述，如果存在两个前缀和模 $k$ 的余数相同的位置 $i$ 和 $j$ （不妨设 $j < i$ ），那么 $\textit{nums}[j+1..i]$ 这个子数组的和是 $k$ 的倍数。

因此，我们可以使用哈希表存储每个前缀和模 $k$ 的余数第一次出现的位置。初始时，我们在哈希表中存入一对键值对 $(0, -1)$ ，表示前缀和为 $0$ 的余数 $0$ 出现在位置 $-1$ 。

遍历数组时，我们计算当前前缀和的模 $k$ 的余数，如果当前前缀和的模 $k$ 的余数没有在哈希表中出现过，我们就将当前前缀和的模 $k$ 的余数和对应的位置存入哈希表中。否则，如果当前前缀和的模 $k$ 的余数在哈希表中已经出现过，位置为 $j$ ，那么我们就找到了一个满足条件的子数组 $\textit{nums}[j+1..i]$ ，因此返回 $\textit{True}$ 。

遍历结束后，如果没有找到满足条件的子数组，我们返回 $\textit{False}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        d = {0: -1}
        s = 0
        for i, x in enumerate(nums):
            s = (s + x) % k
            if s not in d:
                d[s] = i
            elif i - d[s] > 1:
                return True
        return False

speed

复杂度分析

指标	值
时间	complexity is O(n) for a single pass through the array. Space complexity is O(n) to store the first occurrence of each modulo in the hash map. No nested loops are needed, making this approach efficient for large inputs.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Checks if candidate understands prefix sum modulo technique.
question_mark
Observes if candidate handles subarray length edge cases properly.
question_mark
Watches for efficient use of hash map to avoid O(n^2) scanning.

warning

常见陷阱

外企场景

error
Forgetting to check subarray length >= 2 when modulo repeats.
error
Not initializing hash map with 0:-1, causing misses at the array start.
error
Assuming negative numbers or k=0 without proper handling can lead to incorrect modulo logic.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find all subarrays whose sums are multiples of k instead of just one.
arrow_right_alt
Allow k to be zero, requiring direct sum checks instead of modulo.
arrow_right_alt
Return the length of the longest valid subarray rather than a boolean.

help

常见问题

外企场景

继续练习

#1248 统计「优美子数组」#1442 形成两个异或相等数组的三元组数目 #528 按权重随机选择