LC974
和可被 K 整除的子数组
前缀和 · 整除 K可视化:前缀和/积子数组和可被 K 整除个数。
时间 O(n)空间 O(1)
题目1 / 15
题目与输入建立输入、目标与算法心智
子数组和 = prefix[r]-prefix[l-1],查 prefix-k 出现次数
正在加载算法场景...
当前发生了什么
子数组和可被 K 整除个数。
机器状态
prefix mod、map。
为什么正确
prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
不变量
(prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
面试怎么说
前缀 mod K+哈希计数同余前缀,O(n)。
人类输入
子数组和可被 K 整除个数。
机制
prefix mod K;map 存 mod 频次,同 mod 差为 K 倍数。
机器状态
prefix mod、map。
可观察结果
同 mod 前缀差构成 K 倍数子数组个数。
不变量
- · (prefix[j]-prefix[i])%K==0 ⇔ 两前缀 mod K 相同。
常见误区
- · 负数 mod 要 normalize 到 [0,K)。
迁移练习
- · LC560 和为 K
- · LC525 连续数组
面试怎么答
前缀 mod K+哈希计数同余前缀,O(n)。