预计阅读时间：3 分钟

前缀和

前缀和的核心式只有一条：子数组和可以写成两个前缀和之差。记 $s_j$ 为前 j 个元素之和（$s_0 = 0$），第 i 到第 j 个元素（从 1 开始数）的和就是 $\text{sum}(i, j) = s_j - s_{i-1}$。围绕这条式子做变形，就是本合集的全部内容。

前缀和与哈希表

leetcode 523

题意：是否存在长度大于 1 的子数组，其和能被 k 整除。

前缀和的经典问题，务必掌握。把子数组记成第 i+1 到第 j 个元素（长度为 j - i），它的和写成 $s_j - s_i$ 后，「和能被 k 整除」即 $s_j - s_i \equiv 0 \pmod k$，移项立刻得到关键结论：两个前缀和关于 k 同余。

于是一遍扫描：把出现过的前缀和对 k 的余数塞进哈希表，扫到每个新前缀和时 $O(1)$ 查同余的旧前缀和是否存在。哈希表里存余数首次出现的位置 i，查到时 j - i ≥ 2 才满足长度大于 1；只存首次出现，是为了让 j - i 尽量大。

最容易漏的一步：哈希表要先放入空前缀 $s_0 = 0$（余数 0 → 位置 0），否则从第一个元素开始的子数组永远查不到，例如 nums = [2, 4], k = 6 会错答 false。写代码时若用数组下标 j（从 0 开始）记录前缀的末尾，空前缀就记成 {0: -1}，判断条件仍是 j - first[r] >= 2。整体 $O(n)$。

未完待续，本合集随训练进度持续补完。

本文由 aboom 原创，转载请注明出处。