知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 05 - 和可被 K 整除的子数组 ## 题目(LeetCode 974) 给定数组 nums 和整数 k,返回和可被 k 整除的非空子数组数目。 ``` 输入:nums=[4,5,0,-2,-3,1], k=5 输出:7 ``` ## 大白话理解 子数组和可被 k 整除 → `(prefix[j] - prefix[i]) % k == 0` → `prefix[j] % k == prefix[i] % k` 两个前缀和对 k 取模相同,它们之间的子数组和就能被 k 整除。 ## 代码 ```java public int subarraysDivByK(int[] nums, int k) { Map<Integer, Integer> modCount = new HashMap<>(); modCount.put(0, 1); int sum = 0, count = 0; for (int num : nums) { sum += num; // Java 中负数取模可能为负,修正为正 int mod = ((sum % k) + k) % k; count += modCount.getOrDefault(mod, 0); modCount.merge(mod, 1, Integer::sum); } return count; } ``` ### 负数取模的坑 Java 中 `-1 % 5 = -1`,但我们需要的是 `4`。用 `((sum % k) + k) % k` 修正。 ## 复杂度 - 时间:O(n) - 空间:O(k) ## 一句话总结 前缀和取模 + HashMap 计数。模相同的前缀和之间的子数组和能被 k 整除。注意负数取模。 --- 上一篇:[04 - 除自身以外数组的乘积](./04-product-except-self.md) | 下一篇:[06 - 二维区域和检索](./06-range-sum-2d.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入