2.3 累加数组数字求子数组之和

使用双指针解决子数组之和的面试题有一个前提条件——数组中的所有数字都是正数。如果数组中的数字有正数、负数和零，那么双指针的思路并不适用，这是因为当数组中有负数时在子数组中添加数字不一定能增加子数组之和，从子数组中删除数字也不一定能减少子数组之和。

下面换一种思路求子数组之和。假设整个数组的长度为n，它的某个子数组的第1个数字的下标是i，最后一个数字的下标是j。为了计算子数组之和，需要先做预处理，计算从数组下标为0的数字开始到以每个数字为结尾的子数组之和。预处理只需要从头到尾扫描一次，就能求出从下标0开始到下标0结束的子数组之和S₀，从下标0开始到下标1结束的子数组之和S₁，以此类推，直到求出从下标0开始到最后一个数字的子数组之和S_n-1。因此，从下标为i开始到下标为j结束的子数组的和就是S_j-S_i-1。

例如，在数组[1，2，3，4，5，6]中，从下标0开始到下标2结束的子数组[1，2，3]之和是6，从下标0开始到下标4结束的子数组[1，2，3，4，5]之和为15，从下标3开始到下标4结束的子数组[4，5]之和是9，正好15-9=6。

下面用累加数组数字求子数组之和的思路来解决几道典型的算法面试题。

面试题10：和为k的子数组

分析：这个题目看起来也可以利用双指针来解决。我们还是用指针P₁和P₂指向数组中的两个数字，两个指针之间的数字组成一个子数组。如果两个指针之间的子数组的数字之和大于或等于k就向右移动指针P₁，如果子数组的数字之和小于k就向右移动指针P₂。

这个使用双指针的解法基于如下假设：向右移动指针P₂相当于在子数组中添加一个新的数字，从而得到更大的子数组的数字之和。如果新添加的数字是正数，那么这个假设是成立的。但本题中的数组并没有说明是由正整数组成的，因此不能保证在子数组中添加新的数字就能得到和更大的子数组。同样，也不能保证删除子数组最左边的数字就能得到和更小的子数组。

既然双指针的解法不适用于这个题目，就只能尝试其他的解法。下面先分析蛮力法的时间复杂度。在一个长度为n的数组中有O（n²）个子数组，如果求每个子数组的和需要O（n）的时间，那么总共需要O（n³）的时间就能求出所有子数组的和。

如果稍微做一些优化，那么用O（1）的时间就能求出一个子数组的所有数字之和。在求一个长度为i的子数组的数字之和时，应该把该子数组看成在长度为i-1的子数组的基础上添加一个新的数字。如果之前已经求出了长度为i-1的子数组的数字之和，那么只要再加上新添加的数字就能得出长度为i的子数组的数字之和，只需要一次加法，因此需要O（1）的时间。优化之后总的时间复杂度是O（n²）。

下面换一种思路，在从头到尾逐个扫描数组中的数字时求出前i个数字之和，并且将和保存下来。数组的前i个数字之和记为x。如果存在一个j（j＜i），数组的前j个数字之和为x-k，那么数组中从第i+1个数字开始到第j个数字结束的子数组之和为k。

这个题目需要计算和为k的子数组的个数。当扫描到数组的第i个数字并求得前i个数字之和是x时，需要知道在i之前存在多少个j并且前j个数字之和等于x-k。所以，对每个i，不但要保存前i个数字之和，还要保存每个和出现的次数。分析到这里就会知道我们需要一个哈希表，哈希表的键是前i个数字之和，值为每个和出现的次数。

基于计算并保存数组前i个数字之和的思路可以写出如下代码：

上述代码中只有一个循环从头到尾扫描数组一次，因此时间复杂度是O（n）。由于使用一个哈希表保存从第1个数字到当前扫描到的数字之间的数字之和，因此需要O（n）的辅助空间。

面试题11：0和1个数相同的子数组

分析：只要把这个题目稍微变换一下就能重用解决面试题10的解题思路。首先把输入数组中所有的0都替换成-1，那么题目就变成求包含相同数目的-1和1的最长子数组的长度。在一个只包含数字1和-1的数组中，如果子数组中-1和1的数目相同，那么子数组的所有数字之和就是0，因此这个题目就变成求数字之和为0的最长子数组的长度。

和前面的解法类似，可以在扫描数组时累加已经扫描过的数字之和。如果数组中前i个数字之和为m，前j个数字（j>i）之和也为m，那么从第i+1个数字到第j个数字的子数组的数字之和为0，这个和为0的子数组的长度是j-i。

如果扫描到数组的第j个数字并累加得到前j个数字之和m，那么就需要知道是否存在一个i（i＜j）使数组中前i个数字之和也为m。可以把数组从第1个数字开始到当前扫描的数字累加之和保存到一个哈希表中。由于我们的目标是求出数字之和为0的最长子数组的长度，因此还需要知道第1次出现累加之和为m时扫描到的数字的下标。因此，哈希表的键是从第1个数字开始累加到当前扫描到的数字之和，而值是当前扫描的数字的下标。

有了清晰的思路之后再编写代码就比较容易。参考代码如下：

函数findMaxLength中只有一个循环，显然时间复杂度是O（n）。由于需要一个哈希表sumToIndex保存数组中前面若干数字的累加之和，因此空间复杂度也是O（n）。

面试题12：左右两边子数组的和相等

分析：这也是一道关于子数组的和的面试题。假设从头到尾扫描数组中的每个数字。当扫描到第i个数字时，它左边的子数组的数字之和就是从第1个数字开始累加到第i-1个数字的和。此时它右边的子数组的数字之和就是从第i+1个数字开始累加到最后一个数字的和，这个和等于数组中所有数字之和减去从第1个数字累加到第i个数字的和。

如果从数组的第1个数字开始扫描并逐一累加扫描到的数字，当扫描到第i个数字的时候，就可以知道累加到第i个数字的和，这个和减去第i个数字就是累加到第i-1个数字的和。同时，要知道数组中的所有数字之和，只需要从头到尾扫描一次数组就可以。

有了清晰的思路之后再编写代码就比较容易。参考代码如下：

上述代码有两个时间复杂度为O（n）的循环，因此总的时间复杂度为O（n）。函数pivotIndex中只用到了若干临时变量，并没有使用数组、哈希表之类的辅助数据容器，因此空间复杂度是O（1）。

面试题13：二维子矩阵的数字之和

分析：如果不考虑时间复杂度，则采用蛮力法用两个嵌套的循环总是可以求出一个二维矩阵的数字之和。如果矩阵的行数和列数分别是m和n，那么这种蛮力法的时间复杂度是O（mn）。

只是这个题目提到，对于一个二维矩阵，可能由于输入不同的坐标而反复求不同子矩阵的数字之和，这说明应该优化求和的过程，要尽可能快地实现子矩阵的数字求和。

如果仔细分析子矩阵的数字之和的规律，就可以发现左上角坐标为（r₁，c₁）、右下角坐标为（r₂，c₂）的子矩阵的数字之和可以用4个左上角坐标为（0，0）的子矩阵的数字之和求得。图2.2中的阴影部分表示左上角坐标为（r₁，c₁）、右下角坐标为（r₂，c₂）的子矩阵。该子矩阵的数字之和等于左上角坐标为（0，0）、右下角坐标为（r₂，c₂）的子矩阵的数字之和减去左上角坐标为（0，0）、右下角坐标为（r₁-1，c₂）的子矩阵的数字之和，再减去左上角坐标为（0，0）、右下角坐标为（r₂，c₁-1）的子矩阵的数字之和，最后加上左上角坐标为（0，0）、右下角坐标为（r₁-1，c₁-1）的子矩阵的数字之和。

因此，可以在预处理阶段求出从左上角坐标为（0，0）到每个右下角坐标的子矩阵的数字之和。首先创建一个和输入矩阵大小相同的辅助矩阵sums，该矩阵中的坐标（i，j）的数值为输入矩阵中从左上角坐标（0，0）到右下角坐标（i，j）的子矩阵的数字之和。

有了这个辅助矩阵sums，再求左上角坐标为（r₁，c₁）、右下角坐标为（r₂，c₂）的子矩阵的数字之和就变得比较容易。该子矩阵的数字之和等于sums[r₂][c₂]+sums[r₁-1][c₂]-sums[r₂][c₁-1]+sums[r₁-1][c₁-1]。

下面分析如何生成辅助矩阵sums，即求得数组中的每个数字sums[i][j]。按照生成辅助矩阵sums的规则，sums[i][j]的值等于输入矩阵中从左上角坐标为（0，0）到右下角坐标为（i，j）的子矩阵的数字之和。可以把从左上角坐标为（0，0）到右下角坐标为（i，j）的子矩阵的数字看成由两部分组成。第1部分是从左上角坐标为（0，0）到右下角坐标为（i-1，j）的子矩阵，该子矩阵的数字之和等于sums[i-1][j]。第2部分是输入矩阵中第i行中列号从0到j的所有数字。如果按照从左到右的顺序计算sums[i][j]，则可以逐个累加第i行的数字，从而得到子矩阵第2部分的数字之和。

根据上面的分析可以编写出如下所示的Java代码：

如果输入矩阵的行数和列数分别是m和n，那么辅助数组sums的行数和列数分别为m+1和n+1，这样只是为了简化代码逻辑。如果用公式sums[r₂][c₂]+sums[r₁-1][c₂]-sums[r₂][c₁-1]+sums[r₁-1][c₁-1]求解左上角坐标为（r₁，c₁）、右下角坐标为（r₂，c₂）的子矩阵的数字之和，由于坐标值r₁或c₁有可能等于0，因此r₁-1或c₁-1可能是负数，不再是有效的数组下标。如果在矩阵的最上面增加一行，最左面增加一列，这样就不必担心出现数组下标为-1的情形。

函数sumRegion用来求子矩阵的数字之和，该函数只是从数组sums中读取几个数字做加法和减法，因此每次调用的时间复杂度都是O（1）。

类型NumMatrix的构造函数用来做预处理，根据输入矩阵生成辅助矩阵sums。该构造函数使用两个嵌套的循环计算辅助函数sums中的每个数字，因此时间复杂度是O（mn）。同时，数组sums需要的辅助空间为O（mn）。