前缀和算法——部分OJ题详解

（文章的题目解释可能存在一些问题，欢迎各位小伙伴私信或评论指点（双手合十））

关于前缀和算法

前缀和算法解决的是“快速得出一个连续区间的和”，以前求区间和的时间复杂度是O(N)，使用前缀和可以直接降为O(1)

【模板】一维前缀和

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

首先解释下题目：给我们一个长度为n的数组，但是我们要注意数组的下标是从1开始的，不是从0开始的，所以我们创建数组的时候要创建n+1大小的数组。 

然后是最重要的输入参数环节：一共要输入多组数据，分别如下：

1. 第一组数为n和q，n表示要操作的数组长度，上面的示例中为3，q表示要对这个数组操作的次数，示例里为2，表示要进行两次操作，也就是要返回两个结果
2. 第二组输入的数就是要进行操作的数组，长度为n
3. 后面输入几组数据数量为第一组数据的q，示例中q为2，于是后面有两组数，假设q为3，后面就是三组数。后面的这几组数都是2个数组成，分别为l和r，表示left和right
4. 然后就是操作部分，以示例为离，第三组数为1和2，所以就计算数组包含中1下标和2下标的区间内所有值的和，最后输出1+2=3；第四组数为2和3，计算数组中2和3下标区间的和，输出2+4=6。下面来分析下这道题：

1. 首先是暴力解法：其实很简单，首先从指定下标开始，使用循环，循环次数为r-l，然后全部把数相加即可，就是一个简单的模拟。最差情况下，时间复杂度为O(N*q)，绝对会超时，假设10个数，做10次从头加到尾的操作，就是10^10，绝对超时
2. 使用前缀和算法，一般分为两步，第一步：预处理出来一个前缀和数组，用dp表示；第二步：使用前缀和数组。
3. 其中dp里的元素排版是有讲究的，dp[i]表示[1, i]区间内所有元素的和，假设数组为[1, 2, 3, 4]，那么dp数组就是[1, 3, 6, 10]。公式为dp[i] = dp[i - 1] + arr[i]，（这个公式就是动态规划算法里的状态转移方程，以后讲），到这里，第一步“构建前缀和数组”步骤就完成了
4. 然后就是步骤二“使用前缀和数组”，假设目标数组为[1, 2, 3, 4, 5, 6]，要计算的区间为[3, 5]，我们可以先算1到5区间的和，然后再减去1到2区间的和，最后就剩下3到5区间的和了。公式就是:

dp[R] - dp[L - 1]

问题：为什么下标要从1开始计数

解答： 在力扣上给我们的数组下标基本都是从1开始计数。就上面的公式：dp[R] - dp[L - 1]为例，假设计算[0, 2]区间的和，那么公式就是dp[2] - dp[-1]越界了，需要处理边界问题；但是下标从1开始的话就不用处理。

并且由于dp的构成，导致dp[0]这个位置没有数，我们直接设置为0即可，因为0加任何数都等于这个数

#include <iostream>
#include<vector>
using namespace std;
 
int main() 
{
    //1，读入数据
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1); //要n+1，因为下标从1开始
    for(int i = 1; i <= n; i++) cin >> arr[i]; //输入目标数组
 
    //2，构建前缀和数组
    vector<long long> dp(n + 1); //用long long防止溢出
    for(int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i];
 
     //3，使用前缀和
     int l = 0, r = 0;
     while(q--)
     {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;;
     }
     return 0;
}

【模板】二维前缀和

【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

题目和第一题一样，只不过是把要操作的数组从一维变成了二维，后面的操作部分的一组数是4个数，前面两个数和后面两个数各自表示矩阵中的某个数的位置，求由这样两个数对角形成的正方形里所有数的和，其余操作一致，下面来分析下这道题：

1.  首先是暴力解法：直接用两个for循环，直接一个一个算出正方形里的值，很简单。最差情况下，时间复杂度为O(m * n * q)，肯定会超时，所以我们尝试用前缀和算法来解决
2. 步骤一：预处理一个前缀和矩阵出来。前缀和矩阵我们还是命名为dp，长度和宽度也和原矩阵一样，然后就是dp里每个值表示的含义：d[i][j]表示从[1, 1]到[i, j]位置形成的这个正方形里，所有元素的和，如下图：
3. 步骤二：使用前缀和矩阵，还是如下图：
4. 最终，按照上面两个公式来解题，时间复杂度为O(m*n) + O(q)

#include <iostream>
#include<vector>
using namespace std;
 
int main()
{
    //1，读入数据
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> arr[i][j];
 
    //2，构建dp前缀和矩阵
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]; //公式
 
    //3，使用dp前缀和矩阵
    while(q--)
    {
        int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << (dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]) << endl;
    }
    return 0;
}

724.寻找数组的中心下标

724. 寻找数组的中心下标 - 力扣（LeetCode）

题目就不解释了哈，因为感觉我解释得可能还没原题好。下面来分析下这道题：

1. 首先是暴力解法，也是大多数人第一时间想到的算法，假设数组下标为0~n，假设我要判断i这个下标是否是中心下标，要先算0 ~ (i-1)的和，再算(i+1) ~ n-1的和，然后比较两个值是否相等，然后枚举i下标，时间复杂度是O(N^2)，肯定超时
2. 我们可以利用前缀和来优化，下标i左边的和可以直接用前缀和[i-1]来表示，而下标i后面的和可以直接用后缀和[i-1]来表示
3. 我们用 f 来表示前缀和数组 ， g 来表示后缀和数组，其中f[i]表示[0, i-1]区间所有元素的和，g[i]表示[i+1, n-1]区间里所有元素的和
4. f[i] = f[i-1] + nums[i-1]， g[i] = g[i+1] + nums[i+1]，构建前后缀和数组就用这两个公式
5. 然后就是使用这个数组，也就是枚举所有的下标i，然后去判断两个位置是否相等，返回第一个相等时i的值，如果i到结尾了都没有，返回-1

细节问题：

1. 初始化的时候，f[0]需要先赋值为0，不然会越界访问，同理g[n-1]，在公式里就变成了g[n-1] = g[n] + nums[n]，也越界访问了，所以g[n-1]也要赋值为0
2. 然后是填表顺序，在填写f数组的时候是从左往右；但是填g数组的时候是从右往左

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n); //前缀和，后缀和数组
        
        //1，构建前缀和数组和后缀和数组
        for(int i = 1; i < n ; i++)
            f[i] = f[i - 1] + nums[i - 1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i + 1] + nums[i + 1];
 
        //2，使用前缀和数组
        for(int i = 0; i < n; i++) //枚举中心下标
        {
            if(f[i] == g[i]) return i;
        }
        return -1;
    }
};

238.除自身以外数组的乘积

238. 除自身以外数组的乘积 - 力扣（LeetCode）

解释下题目：给我们一个数组nums，让我们再构建一个数组answer返回，其中answer数组的answer[i]表示的含义是在nums中除nums[i]以外的其余各元素的和，相乘时题目保证不会溢出。下面来解释下这道题：

1. 暴力解法也很简单，就枚举每一个位置，让后把其余值都相乘再记录，和前面题目的暴力解法一样，会超时哦，所以我们来尝试用前缀和来解决这道题：
2. 这道题由于是求乘积，所以我们也可以叫做前缀积，所以需要对前面的前缀和模板大改一下，并且也要有后缀积
3. 步骤一，预处理前缀积和后缀积：用 f 表前缀积， g 表示后缀积。首先f[i]只要表示[0, i-1]区间的积即可，所以f[i] = f[i-1] * nums[i-1]；然后g[i]表示[i+1, n-1]，所以g[i] = g[i+1] * nums[i+1]
4. 步骤二，使用前缀数组：先构建ret目标数组，然后填这个数组就好了，非常简单，ret[i] = f[i] * g[i]

处理细节问题：

• 和上面一样又不一样，f(0) = 1，g(n-1) = 1

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);
        f[0] = g[n-1] = 1;
 
        //1，构建前缀积和后缀积数组
        for(int i = 1; i < n; i++)
            f[i] = f[i-1] * nums[i-1];
        for(int i = n - 2; i >= 0; i--)
            g[i] = g[i+1] * nums[i+1];
        
        //2，使用
        vector<int> ret(n);
        for(int i = 0; i < n; i++)
            ret[i] = f[i] * g[i];
        
        return ret;
    }
};

560.和为K的子数组 

560. 和为 K 的子数组 - 力扣（LeetCode）

题目描述很简单，并且上面的示例很好懂，下面来解释下这道题：

1.  首先是暴力解法：就是暴力枚举，因为只要涉及到“子数组”，暴力解法95%以上都是枚举所有子数组，然后一一判断，而且就算我们找到这个位置后也不能停止，因为数组元素是包含负数的，所以正负可能抵消掉，时间复杂度为O(N^2)，超时
2. 这道题不能用滑动窗口或双指针来优化，因为用滑动窗口做优化时，找到一种结果，一个区间后，left和right就移动了，但是假设我们以[-1, 1, 3, 2, -2]为例，假设滑动窗口找到了这个区间，但是我们可以发现，-1和1，2和-2是可以抵消的，所以就会出现在一个符合要求的区间内还有一个或多个符合要求的子区间，这样的情况滑动窗口是搞不了的（不能用双指针本质是因为包含负数）
3. 求区间和，可以用前缀和算法。暴力算法的本质就是，以某个位置为“起点”枚举的所有子数组，不关心结尾；我们可以反过来，以某一个位置为“结尾”枚举子数组，反过来向前枚举，不关心开头在哪。
4. 

细节问题：

• 首先是前缀和假如哈希表的时机：先把所有前缀和全算出来，然后全扔哈希表里去。这个方法不行的，我们要算的是i位置之前的前缀和等于K的数量，全扔进去的话可能会统计到i位置之后的；所以在计算i位置之前，哈希表里只保存[0, i - 1]位置的前缀和
• 我们其实不用创建一个前缀和数组：在计算dp[i]时，原先的公式是：dp[i] = dp[i-1] + nums[i]，但是我们可以不创建前缀和数组，所以我们可以用以后个变量sum来标识dp[i-1]，然后公式就可以写成dp[i] = sum + nums[i]; sum = dp[i]，依次循环，就可以不创建前缀和数组从而求出前缀和
• 如果整个前缀和等于K呢？假设一个区间[0, i]为K，所以按照前面的思路应该就算去[0, -1]这个区间去找和为0的区间，但是不存在-1区间，但是这也是一种情况，不能忽略。所以写代码时创建哈希表时，要先hash[0] = 1，避免“整个数组前缀和为K”这种情况被忽略

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash; //统计前缀和出现的次数
        hash[0] = 1;
 
        int sum = 0, ret = 0;
        for(auto x : nums)
        {
            sum += x; //计算当前位置的前缀和
            if(hash.count(sum - k)) ret += hash[sum - k]; //如果该前缀和符合要求，就统计该前缀和出现的次数
            hash[sum]++;
        }
        return ret;
    }
};

974.和可被K整除的子数组

974. 和可被 K 整除的子数组 - 力扣（LeetCode）

这道题是某一年蓝桥杯竞赛原题，先解释下题目：这道题描述和上面“和为K的子数组”很像，给一个整数数组nums和一个整数K，要求我们返回连续的子数组，该子数组的要求是，子数组元素的和可被K整除。下面来分析下这道题：

补充下知识：

1. 同余定理：就算一个数学公式：(a - b) / p = k 余零，那么我们可以认为：a % p == b % p。举个例子：(26 - 12) / 7 = 2 余零，那么可以得出 (26 % 7) == (12 % 7) == 5。取余的本质其实就算让一个数不断的减另一个数，以7 % 2为例：7 % 2 = (7 - 2 -2 -2) = 1，所以我们也可以看作(1 + 2 * 3) % 2 = 1，所以我们就又可以得出一个公式：(a + p * k) % p = a%p。
2. C++， java 负数% 正数的结果以及修正：

下面来分析下这道题，解题思路和上面一道题很像

1. 解法一就算暴力枚举：和上一道题非常相似，并且存在负数所以也不能用滑动窗口来优化，所以我们还是尝试用前缀和 + 哈希表来优化
2. 

class Solution 
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int, int> hash; //统计前缀和出现的次数，第一个int为前缀和余数，第二个int表示次数
        hash[0] = 1; //0的余数只能是0，所以要单独处理一下
 
        int sum = 0, ret = 0;
        for(auto x : nums)
        {
            sum += x; //计算当前位置的前缀和
            int r = (sum % k + k) % k; //计算前缀和余数，修正后的余数
            if(hash.count(r)) ret += hash[r]; //如果该前缀和余数符合要求，就统计该前缀和余数出现的次数
            hash[r]++;
        }
        return ret;
    }
};

 525.连续数组

 525. 连续数组 - 力扣（LeetCode）

解释下题目：给一个二进制数组，这个数组只有0和1两种元素，找到含有相同数量的0和1的最长子数组，返回长度。题目很简单，下面来分析下这道题：

1. 这道题如果用最普通的办法就是枚举子数组然后统计0和1的个数来比较，其实很不好搞，所以还是正难则反，我们可以先将所有的0改为“-1”，那么题目就可以变成找出最长的子数组使子数组中所有元素的和为0即可

处理细节：

1. 哈希表里存什么？在这道题里，我们不关心前缀和有多少个，我们只关心你的长度，所以<int, int>，第一个int还是前缀和不变，第二个int不存个数了，存的应该是下标
2. 什么时候存入哈希表？在sum和下标i使用完成之后再扔哈希表里去
3. 如果出现重复的<sum, i>，如何存？当 i = 9时，sum符合要求，但是假设当j = 4时，sum也符合要求，这时，我们应该选择更靠前的下标，因为下标越靠前，算出来的子数组越长哦，所以要存<sum, j>
4. 默认的前缀和的和为0的情况，如何存？当整个数组的sum为0时，我们是要在nums[-1]这个位置寻找前缀和为0的数组的，因此在上一道题里面我们是hash[0] = 1，表示默认有一个前缀和为0的，表示前缀和为0的数组有一个，上面那一道题村的是个数，这道题我们要存的是下标，所以这道题我们要hash[0] = -1
5. 长度怎么算？

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int, int> hash; //细节1
        hash[0] = -1; //细节4
 
        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); i++)
        {
           if(nums[i] == 0) sum += -1; //将0变成-1
           else sum += 1;
           if(hash.count(sum)) ret = max(ret, i - hash[sum]); //细节3，推导长的那一个数组的长度
           else hash[sum] = i; //如果存在相同的sum，就更新长的那一个数组，如果是新的sum，就扔哈希表里去
        }
        return ret;
    }
};

1314.矩阵区域和

1314. 矩阵区域和 - 力扣（LeetCode）

前面的都是一维前缀和题目，是时候做一下二维前缀和了。题目如下图： 下面来解释下这道题：

1. 这道题明显就算要求我们快速求出矩阵中某一个区间的和，所以就要用到我们的“二维前缀和算法”，关于二维前缀和可以再划到前面第二题去复习一下。初始化前缀和矩阵的公式为：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i][j]；使用公式为：假设我们要求的最终结果为ret = dp[x2][y2] = dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]
2. 回到本题，我们要计算answer[i][j]的值，我们首先要知道[i][j]对应得mat矩阵中选中得子矩阵的左上角左边和右下角坐标，这个其实很好找，根据延申规则来即可，公式为：左上角坐标 = [i - k][j - k]；右下角坐标 = [i + k][j + k]，由于计算后得坐标可能会越界，如下图：
3. 还有一个重要的关系，就是下标的映射关系：在第一和第二题中，牛客提供给我们的数组和下标都是从1开始的，规避了边界情况，但是力扣给我们的都是从0开始的；简单来说，假设我们的dp矩阵要填的位置是(x, y)，那么这个位置的值我们需要从原矩阵mat的(x-1, y-1)去找的，原数组下标从1开始的话没问题，因为第0行和第0列的值默认为1，构建dp时正常的；但是当原矩阵下标从0开始，由于0-1 = -1，所以就会有非常非常非常多的边界情况需要处理，代码写起来会又难又长。所以我们前面的初始化dp[i][j]的公式就要稍微修改下：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i - 1][j - 1]
4. 然后在使用的时候，还有一个地方需要注意：answer矩阵也是从0开始计数的，当填充answer[x][y]这个位置的值时，要去dp矩阵中找数，那么找的应该就是dp[x + 1][y + 1]，但是对应到上面的ret公式里的话，就要全部加1，太麻烦，所以我们可以直接在求坐标的时候就+1，如下图：

class Solution 
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m = mat.size(), n = mat[0].size(); //计算原矩阵的长和宽大小
        
        //1，构建前缀和dp矩阵
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
 
        //2，使用前缀和矩阵
        vector<vector<int>> ret(m, vector<int>(n));
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
            {
                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        return ret;
    }
};