前缀和 — 利用前缀信息解决子数组问题

【前缀和的核心思想是预先处理数组来快速计算任意子数组的和，基本上用于数组和序列问题。】

前缀和算法具体步骤

1. 构造前缀和数组：

   • 给定一个数组nums，其前缀和数组prex定义为prex[i]表示为数组nums从起始位置到第i个位置的元素累加和。
   • 构建前缀和公式：

   $$\begin{gathered} prex[i]=nums[i](i==0) \\ prex[i]=prex[i-1]+nums[i](i>0) \end{gathered}$$

2. 快速计算子数组和：

   • 一旦前缀和数组构建完成，就可以快速计算任意子数组nums[i...j]的元素累加和。

   $$sum(nums[i...j])=prex[j]-prex[i-1](i>0)$$

   • 当i == 0时，子数组和也就是nums[0]。

我们前面介绍过【滑动窗口算法】，滑动窗口算法也是基本用于数组和序列问题的，所以我们把【前缀和算法】与【滑动窗口算法】放在一起研究，也当作对滑动窗口算法的复习。

简要复习一下滑动窗口算法的步骤

【滑动窗口算法的核心思想就是维护一个固定长度的窗口，在数组或序列上滑动以满足某些条件。通常用于解决最大子数组和、最小子数组和等问题。】

1. 初始化窗口：

   设置窗口的起始和结束指针。

2. 滑动窗口：

   移动窗口的起始和结束指针，依据问题的要求调整窗口的大小，维护窗口的状态（例如窗口内元素的和，最大值，最小值等）。

[!TIP]

之前我们分析滑动窗口算法的时候就提到过，选择哪种数据结构来存储数据需要根据【窗口内的数据以及数据的处理形式】来考虑。

比如：

• 如果需要记录窗口中各字符以及各字符出现的次数，就用哈希表。

我们通过一个例子看深入了解一下前缀和算法：

LeetCode560 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

暴力解法

既然是找满足条件的子数组个数，那我们可以枚举所有的子数组，然后选出符合条件的子数组就行了。

int subarraySum(vector<int> &nums, int k) {
    int size = nums.size();
    int result = 0;
    for (int left = 0; left < size; left++) {
        for (int right = left; right < size; right++) {
            //这个时候窗口为 nums[left...right]
            int sum = 0;
            int cur = left;
            while (cur <= right) {
                sum += nums[cur];
                cur++;
            }
            if (sum == k)result++;
        }
    }
    return result;
}

暴力解法就是这么通俗易懂，找出每个子串，然后对每个子串单独进行分析就行了。但是暴力解法找子串的时间复杂度是$$O(N^2)$$​,时间复杂度太高了，所以我们需要思考另一种解法。

前缀和分析思路：

联想刚刚学到的前缀和表示子数组，我们知道，子数组nums[i...j]之和不就是prex[j] - prex[i-1]嘛。也就是说，和为 K 的子数组满足等式

$$prex[j]-prex[i-1]==K$$

但是按照这个等式思路，我们只是利用了前缀和来方便找出各个子串的和罢了，还是要变动i,j两个变量来查找和为 K 的子数组，时间复杂度还是$$O(N^2)$$，我们得到目标是什么？是要降低时间复杂度。很容易想到，既然变动两个变量的时间复杂度为$$O(N^2)$$,那我们就试试只变动一个变量，我们对上面公式进行变换：

$$prex[i-1]==prex[j]-K$$

从这个公式，我们清楚，如果子串最右边字符的位置j确定，那么要想找到【和为 K 的子数组】的个数，只需找到前缀和数组中0,1,...j-1这些位置对应的值中有几个值等于$$K-prex[j]$$, 如果我们把这个查找的实践复杂度降为$$O(1)$$，那么总体的时间复杂度只消耗在j的变动上了嘛，也就降为了$$O(N)$$。

怎么实现这个查找呢？和滑动窗口算法一样，面对不同的数据组织和变动情况，我们要选择合适的数据结构来帮助我们存储和查找数据。在这个题目中，因为要存储0,1,...,j-1的前缀和以及前缀和出现的次数，所以我们使用哈希表来存储数据，键代表j之前的各个前缀和，值代表此前缀和对应的数组出现的次数。

分析了这么多，最后我们只要移动j就行了，只需要对数组遍历一次。

我们给出前缀和解法：

int subarraySum(vector<int> &nums, int k) {
	//计数器，存储j之前数组和以及数组和出现的次数
    unordered_map<int,int> mp;
    mp[0]++; //数组为空，和自然为0
    int prex[nums.size()];
    int result = 0;

    for(int j = 0; j < nums.size(); j++){
        if(j == 0){
            prex[j] += nums[j];
            //查找j之前的数组和有几个满足条件
            if(mp.count(prex[j] - K)){
                result += mp[prex[j] - K];
            }
            mp[prex[j]]++;
            continue;
        }
        prex[j] = prex[j-1] + nums[j];
        if(mp.count(prex[j] - K)){
                result += mp[prex[j] - K];
        }
        mp[prex[j]]++;
    }
    return result;
}

这段代码便是我们利用【前缀和】和【哈希表】得到的解法，时间复杂度是降低了，空间复杂度能降低吗？

复盘这段代码，我们发现，在循环里，第'j'次循环只用到了prex[j]并不会用到前面的prex[0...j-1]，所以我们不用再花费$$O(N)$$的空间复杂度去维护前缀和数组prex[]，直接用一个变量prex表示prex[j]即可。

改造后的代码：

int subarraySum(vector<int> &nums, int k) {
	//计数器，存储j之前数组和以及数组和出现的次数
    unordered_map<int,int> mp;
    mp[0]++; //数组为空，和自然为0
	int prex = 0;
    int result = 0;

    for(int num : nums){
        prex += num;
        if(mp.count(prex - K)){
           result += mp[prex - K];
        }
        mp[prex]++;
    }
    return result;
}

到这里，你基本上掌握了前缀和的思想了，但是要注意的是：

[!IMPORTANT]

前缀和只是我们用来表示子数组的一种方法而已，遇到具体问题，我们要找出问题的本质，子数组间有什么关系？最好能找出具体公式出来，比如这道【和为 K 的子数组】题目，我们就是找出了公式

$$prex[j]-prex[i-1]==K$$

之后对这个公式进行分析，进行合适的变换。

1248 454

【我们再看两道题来巩固一下【前缀和】与其他数据结构结合的算法思想】

LeetCode523 连续的子数组

一个 好的子数组 是：

• 长度 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

注意：

• 子数组 是数组中 连续 的部分。
• 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 1^09
• 0 <= sum(nums[i]) <= 2^31 - 1
• 1 <= k <= 2^31 - 1

分析过程：

这道题算是【和为 K 的子数组】的变式，求【和为 K 的整数倍的子数组】，我们先考虑迁移【和为 K 的子数组的解法】。

得出公式：

$$\begin{gathered} prex[j]-prex[i-1]==\lambda \ast K \\ prex[i-1]==prex[j]-\lambda \ast K \end{gathered}$$

解法框架如下：

bool checkSubarraySum(vector<int> &nums, int k) {
	//计数器，存储j之前数组和以及数组和出现的次数
    unordered_map<int,int> mp;
    mp[0]++; //数组为空，和自然为0
	int prex = 0;
    int result = 0;

    for(int num : nums){
        prex += num;
        if(mp.count(prex - lamda*K)){
        	result += mp[prex - lamda*K];
        }
        mp[prex]++;
    }
    return result > 0;
}

我们怎么确定这个$$lamda$$呢？要枚举$$lamda$$的取值并代入吗？$$lamda$$取值为$$0,...,[prex/X]$$。或者遍历mp里的每个键，查看prex是否能整除X。

上面的分析只分析了子数组的数组和可能为 K 的倍数，子数组的长度至少为 2，这个要求我们并没有考虑。和子数组长度有关的话，哈希表存储前缀和以及前缀和出现的次数就不能用了，因为哈希表里的前缀和nums[0...i]并不能确定是i是什么，我们只是将前缀和的值一股脑放进哈希表里而已。

所以我们现在要改变数据存储形式，要么使用别的数据结构，要么将哈希表里的键值对对应的数据改为其他数据。所以现在，我们要体现出【前缀和】，以及【前缀和对应的位置nums[0...i](i)】和【出现的次数】。怎么体现呢？按照之前思路，我们是在遍历prex[j]，在遍历的同时，将{前缀和:{位置，出现次数}}存入哈希表中。

解法如下：

bool checkSubarraySum(vector<int> &nums, int k) {
	//计数器，存储j之前数组和以及数组和出现的次数
    unordered_map<int,pair<int,int>> mp;
    mp[0] = {-1,1}; //数组为空，和自然为0
	int prex = 0;
    int result = 0;

    for(int j = 0;j < nums.size();j++){
        prex += nums[j];
        //遍历哈希表，查看是否存在这样一个前缀和，使得prex与这个前缀和之差是K的倍数,且满足长度大于等于2
        for(const auto& element : mp){
            if((prex - element.first)% k == 0){
                if(element.second.first < j - 1){
                    result += element.second.second;
                }
            }
        }
        mp[prex] = {j,mp[prex]+1}; //?
    }
    return result > 0;
}

接下来看看二维以及多维的前缀和是如何使用的

二维前缀和

【二维前缀和】和【一维前缀和】一样，也是记录前面数组元素的累加和。对于一维而言，就是前$$0,1,...,i-1$$这些位置对应的元素的累加和，二维也是一样，前$$0<=m<i,0<=n<j,(m,n)$$ 这些位置对应的元素累加和，其实也就是以$$(i,j)$$​ 为右下角的正方形左上方的所有元素之和。同样，我们给出二维前缀和数组以及递推公式：

二维前缀和具体步骤

1. 构建二维前缀和数组

   • 给定一个二维数组matrix，其前缀和数组定义为preSum[i][j]表示以(0,0)为左上角，(i,j)为右下角的矩形内所有元素之和。
   • 构建二维前缀和公式：

   $$\begin{gathered} preSum[0][0]=matrix[0][0] \\ preSum[0][j]=preSum[0][j-1]+matrix[0][j](i==0,j>0) \\ preSum[i][0]=preSum[i-1][0]+matrix[i][0](i>0,j==0) \\ preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+matrix[i][j](i>0,j>0) \end{gathered}$$

2. 优化后的二维前缀和数组

   我们发现，上面的二维前缀和公式过于麻烦，需要分类讨论四种情况，这四种情况都是边界处的情况。所以我们现在弱化边界，在边界之外再套一层，在原来的二维数组左上方套一层，套上的每一个元素都是 0，这样就不会影响前缀和数组的数值。

   • 优化后的数组定义：preSum[i][j]表示以(0,0)为左上角，(i-1,j-1)为右下角的矩形内所有元素之和。preSum[0][0...n],preSum[0...n][0]这些元素都赋值 0，这也就是我们上面说的套上一层辅助数据，这些数据都是 0。
   • 二维前缀和公式：

   $$preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+matrix[i-1][j-1](i>=1,j>=1)$$

   优化后的数组，preSum[i][j]对应matrix[i-1][j-1]为右下角的矩形元素累加和。

3. 快速计算区域子矩阵和（多维数组叫着有点别扭，后面都会用矩阵代替多维数组）

   得出前缀和矩阵后，我们可以利用前缀和矩阵快速计算出子矩阵中元素累加和。如果子矩阵的左上角为(m,n),右下角为(i,j)，那么我们可以直接利用公式：

   $$SubMatrixSum=preSum[i][j]-preSum[i][n-1]-preSum[m-1][j]+preSum[m-1][n-1]$$

   这里是利用了优化后的前缀和数组来进行分析，i,j的取值为$$\mathrm{1...}n$$。

我们来看一道题目，充分理解二维前缀和

LeetCode1314 矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

问题分析：

我们很容易看出，answer[i][j]表示的就是以[i][j]为中心，边长为$$2\ast k+1$$的正方形内的所有元素之和。对照刚刚讲的二维前缀矩阵，这个正方形可以由什么表示呢？

int start_i = std::max(i-k,0);
int start_j = std::max(j-k,0);
int end_i = std::min(m-1,i+k);
int end_j = std::min(n-1,j+k);

其实这个“正方形”中的元素就是以start_i,start_j为左上角，end_i,end_j为右下角的矩形中的所有元素。answer[i][j]存的就是这个矩形中所有元素的累加和嘛。这个累加和我们直接用递推公式就可以得出来：

$$\begin{gathered} SubMatrixSum=preSum[en{d}_i+1][en{d}_j+1]-preSum[en{d}_i+1][star{t}_j-1+1] \\ -preSum[star{t}_i-1+1][en{d}_j+1]+preSum[star{t}_i-1+1][star{t}_j-1+1] \end{gathered}$$

这里的(i,j)是基于原矩阵matrix的。

现在我们给出最终代码：

vector <vector<int>> matrixBlockSum(vector <vector<int>> &mat, int k) {
    int m = mat.size();
    int n = mat[0].size();
    vector <vector<int>> answer(m, vector<int>(n));
    //创建前缀和矩阵
    int preSum[m + 1][n + 1];
    for (int j = 0; j <= n; j++) {
        preSum[0][j] = 0;
    }
    for (int i = 0; i <= m; i++) {
        preSum[i][0] = 0;
    }
    //为前缀和矩阵赋值
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            preSum[i + 1][j + 1] = preSum[i][j + 1] + preSum[i + 1][j]
                                   - preSum[i][j] + mat[i][j];
        }
    }
    //为answer矩阵赋值
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int start_i = std::max(i-k,0);
            int start_j = std::max(j-k,0);
            int end_i = std::min(m-1,i+k);
            int end_j = std::min(n-1,j+k);
            answer[i][j] = preSum[end_i + 1][end_j + 1] - preSum[end_i + 1][start_j]
                           - preSum[start_i][end_j + 1] + preSum[start_i][start_j];
        }
    }
    return answer;
}

注意！！！，前缀和只是一种求子数组和子矩阵的方法而已，当遇到需要求解子数组或者子矩阵的问题时，如果需要用到子数组或者子矩阵中的元素，可以使用前缀和来表示子数组或者子矩阵。