一、什么是前缀和?

对于一个给定的数列 \(A\) ,它的前缀和数列 \(S\) 中 \(S_{[i]}\) 示意从第 \(1\) 个元素到第 \(i\) 个元素的总和。用公式示意为:

$$S_{[i]}=\sum_{j=1}^iA[j]$$
代码如下:

$S = [0];for ($i=0;$i<count($arr);$i++) {    $S[$i+1] = $S[i] + $arr[$i];}

二、前缀和的利用

和为K的子数组
给定一个整数数组和一个整数 k,能够找到该数组中和为 k 的间断的子数组的个数。

三、前缀和的示例

(一)问题形容

给定一个整数数组和一个整数 k,你须要找到该数组中和为 k 的间断的子数组的个数。

输出:$nums = [1,6,2,5,4,2]; $k = 8;输入:1。(间断子数组为[6,2])
(二)问题剖析

(1)先从相熟的数列开始:

数列\( \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$$

进行形象:如果要求间断子数列 \( a_i,\cdots,a_j \) 的和,则能够用数列前 j 项的和减去数列前 \( i-1 \) 项的和:

$$ S_j - S_{i-1} = a_i + a_{i+1} +...+a_j $$

(2)回到数组,数组的下标是从 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=>n,...,S_{j-1}=>n]$$

联合 \(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=1+6+2=9\)。

此时 \(S_3 - k = 9 - 8 = 1\),即前 3 项和与 k 的差值为 1。

此时的前缀和数组为 \([0=>1,1(S_1)=>1,7(S_2)=>1]\)。而 \(S_3\) 与 k 的差值 1 为前缀和数组的键 \(S_1\),故更新答案。

于是就将是否存在和为 k 的间断子数组的问题转化为了 \(S_j - k\) 的值是否为前缀和的键的问题。

(三)参考代码
function prefix($arr, $k){    $prefix = [0=>0];    $ans    = 0;    $sum_j  = 0;    // 在数组的最后面增加了 0 元素。    array_unshift($arr, 0);    // 增加 0 元素之后,就从下标 1 开始加。    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)\)。

五、相似问题

1. 向下的门路节点值之和

参考资料

1. 前缀和

2. 前缀和技巧

3. 什么是前缀和?