前缀和
前缀和的核心式只有一条：子数组和可以写成两个前缀和之差，$\text{sum}(i, j) = s_j - s_{i-1}$。围绕这条式子做变形，就是本合集的全部内容。
前缀和与哈希表
leetcode 523
题意：是否存在长度大于 1 的子数组，其和能被 k 整除。
前缀和的经典问题，务必掌握。子数组和写成 $s_j - s_i$ 后，「和能被 k 整除」即 $s_j - s_i \equiv 0 \pmod k$，移项立刻得到关键结论：两个前缀和关于 k 同余。
于是一遍扫描：把出现过的前缀和对 k 的余数塞进哈希表，扫到每个新前缀和时 $O(1)$ 查同余的旧前缀和是否存...