LeetCode 题解工作台
和可被 K 整除的子数组
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。 子数组 是数组中 连续 的部分。 示例 1： 输入： nums = [4,5,0,-2,-3,1], k = 5 输出： 7 解释： 有 7 个子数组满足其元素之和可被 k = 5 整除： [4, …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
假设存在 $i \leq j$，使得 的和能被 整除，如果我们令 表示 的和，令 表示 的和，那么 $s_j - s_i$ 能被 整除，即 $(s_j - s_i) \bmod k = 0$，也即 $s_j \bmod k = s_i \bmod k$。因此，我们可以用哈希表统计前缀和模 的值的个数，从而快速判断是否存在满足条件的子数组。 我们用一个哈希表 统计前缀和模 的值的…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。
示例 1：
输入：nums = [4,5,0,-2,-3,1], k = 5 输出：7 解释： 有 7 个子数组满足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:
输入: nums = [5], k = 9 输出: 0
提示:
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 1042 <= k <= 104
解题思路
方法一：哈希表 + 前缀和
假设存在 ，使得 的和能被 整除，如果我们令 表示 的和，令 表示 的和，那么 能被 整除，即 ，也即 。因此，我们可以用哈希表统计前缀和模 的值的个数，从而快速判断是否存在满足条件的子数组。
我们用一个哈希表 统计前缀和模 的值的个数，即 表示前缀和模 的值为 的个数。初始时 。用变量 表示前缀和，初始时 。
接下来，从左到右遍历数组 ，对于遍历到的每个元素 ，我们计算 ，然后更新答案 ，其中 表示前缀和模 的值为 的个数。最后我们将 的值加 ，继续遍历下一个元素。
最终，我们返回答案 。
注意，由于 的值可能为负数，因此我们可以将 模 的结果加上 ，再对 取模，以确保 的值为非负数。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def subarraysDivByK(self, nums: List[int], k: int) -> int:
cnt = Counter({0: 1})
ans = s = 0
for x in nums:
s = (s + x) % k
ans += cnt[s]
cnt[s] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n + k) |
| 空间 | O(k) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of prefix sums and how they relate to solving modular arithmetic problems in subarrays.
- question_mark
The candidate effectively applies hash maps for optimized lookups, showcasing an ability to avoid brute force solutions.
- question_mark
The candidate handles edge cases, ensuring their solution works even for small arrays and corner scenarios.
常见陷阱
外企场景- error
Failing to account for negative numbers when calculating modulo values, which can lead to incorrect results.
- error
Overcomplicating the problem by attempting nested loops or brute force approaches when hash maps can provide a more efficient solution.
- error
Not handling the case where the sum of the subarray itself is divisible by k, especially for the first element of the array.
进阶变体
外企场景- arrow_right_alt
Given an array and a divisor, count the number of subarrays whose sum is divisible by a different integer or set of integers.
- arrow_right_alt
Modify the problem to find the longest subarray whose sum is divisible by k.
- arrow_right_alt
Instead of divisibility, solve for subarrays whose sum is a multiple of k or meets other modular constraints.