一、什么是前缀和？
对于一个给定的数列 $A$，它的前缀和数列 $S$ 中 $S_{[i]}$ 示意从第 $1$ 个元素到第 $i$ 个元素的总和。用公式示意为：
$$S_{[i]}=\sum_{j=1}^iA[j]$$
二、前缀和的利用
和为 K 的子数组
给定一个整数数组和一个整数 k，能够 找到该数组中和为 k 的间断的子数组的个数。
三、前缀和的示例
（一）问题形容
给定一个整数数组和一个整数 k，你须要找到该数组中和为 k 的间断的子数组的个数。
输出：$nums = [1,6,2,5,4,2]; $k = 8;
输入：1。（间断子数组为[6,2]）（二）问题剖析
先从相熟的数列开始：
数列 $\lbrace a_n \rbrace$
$$a_1,a_2,a_3,…,a_{n+1},…$$
数列的前 n 项和：
$$S_n=a_1+a_2+a_3+\ldots+a_{n-1}+a_{n}$$
例如，求数列的前 3 项和 $S_3 = a_1 + a_2 + a_3$，数列的前 7 项和 $S_7 = a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7$。
如果要求间断子数列 $ a_4,a_5,a_6,a_7 $ 的和。能够用数列的前 7 项和减去数列的前 3 项和。即：
$$S_7 – S_3 = a_4 + a_5 + a_6 + a_7;$$
进行形象：如果要求间断子数列 $ ai,\cdots,aj $ 的和，则能够用数列前 j 项的和减去数列前 $i-1$ 项的和：
$$ S_j – S_{i-1} = a_i + a_{i+1} +…+a_j $$
回到数组，数组的下标是从 0 开始的：
$$\$arr = [a_0,a_1,a_2,…,a_{n+1},…]$$
数组的前 3 项和，理论是从 $\$arr[0]$ 始终加到 $$arr[2]$，即：$S_3 = $arr[0] + $arr[1] + $arr[2]$。
以防搞混，在数组的最后面增加一个 0 元素，即 $[0=>0,1=>a_0,2=>a_1,…]$，相当于所有的元素都往后挪了一个地位。这样既不会影响后果，又和解决数列的办法同步。
此时，数组的前 7 项和就等于：
$$S_7=\$arr[1] + \$arr[2] + \$arr[3] + \$arr[4] + \$arr[5] + \$arr[6] + \$arr[7]$$
进行形象，在数组的最后面增加 0 元素之后，求数组的间断子数组 $arr[i,…,j]$ 和的办法与数列雷同，其中 $1 \le i \le j \lt len，其中 i、j 都为整数 $：
$$ S_j – S_{i-1} = \$arr[i] + \$arr[i+1] +…+\$arr[j] $$
如果某个间断子数组 $arr[i,..,j]$ 的和为题目所给的 k，则有：
$$ S_j – S_{i-1} = \$arr[i] + \$arr[i+1] +…+\$arr[j] = k$$
即：
$$ S_j – S_{i-1} = k $$
对其进行移项：
$$ S_{i-1} = S_j – k $$
$i – 1$ 的范畴是什么？由 $1 \le i \le j \lt len$ 的范畴可知：
$$0 \le i-1 \le j-1 \lt len$$
当遍历到第 j 项时，前 j 项的和 $S_{j}$ 就曾经确定了。而 k 又是一个常数，换句话说 $S_{j} – k$ 是一个定值。此时前缀和数组中保留了数组的前 1 项和 $S_1$，前 2 项和 $S_2$，…，前 j-1 项和 $S_{j-1}$。即：
$$[0=>1,S_1=>1,…,S_{j-1}=>1]$$
联合 $i-1$ 的取值范畴与前缀和数组的键可知，如果 $S_{i-1} = S_j – k$ 成立，那么 $S_{i-1}$ 肯定是前缀和数组的某个键，具体是哪个键无关紧要。
例如，在输出的数组的最后面增加了 0 元素后：$\$arr = [0,1,6,2,5,4,2]$，当遍历到第 3 项时（起始的下标为 1，而非 0），$S_3=9$。此时的前缀和数组为 $[0=>1,1(S_1)=>1,7(S_2)=>1]$，$S_3 – k = 9 – 8 = 1$。而 1 为前缀和数组的键 $S_1$，故更新答案。
于是就将是否存在和为 k 的间断子数组的问题转化为了 $S_j – k$ 的值 是否为前缀和的键的问题。
（三）参考代码
function prefix($arr, $k)
{$prefix = [0=>0];
$ans = 0;
$sum_j = 0;
array_unshift($arr, 0);
for ($j=1;$j<count($arr);$j++) {$sum_j += $arr[$j];
$sum_i = $sum_j - $k;
if (array_key_exists($sum_i, $prefix)) {$ans++;}
$prefix[$sum_j] = getOrDefault($prefix, $sum_j) + 1;
}
return $ans;
}
function getOrDefault($arr, $key, $default = 0)
{
// 辅助函数，通过键获取关联数组的值。// 如果键存在则返回该键的值，如果不存在则返回 默认值。if (array_key_exists($key, $arr)) {return $arr[$key];
} else {return $default;}
}
$arr = [1,6,2,5,4,2];
$k = 8;
$re = prefix($arr, $k);
var_dump($re); // 1四、复杂度剖析
只用了一个循环，所以工夫复杂度为 $O(n)$。
五、相似问题
- 向下的门路节点值之和
参考资料
- 前缀和
- 前缀和技巧
- 什么是前缀和?