算法技巧之前缀和

一、什么是前缀和？

对于一个给定的数列 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

进行抽象：假如要求连续子数列 ai,\cdots,aj 的和，则可以用数列前 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. 什么是前缀和?

本作品采用《CC 协议》，转载必须注明作者和本文链接