【优选算法】Prefix-Kage：前缀和的算法影（下）

本篇是前缀和算法的实战篇，有一定难度，相信耐心看完会有别样的收获：）

1.前缀和+后缀和

1.1 寻找数组的中心下标

✏️题目描述：

✏️示例：

传送门：寻找数组的中心下标

题解:
💻第一步： 要计算前后和相等的数的下标（不包括该数），显然要计算前后缀和

假设符合题意的数的下标为 i，那么其前后数的下标就很容易推导出来了。我们小学的时候就学过函数，那么前后和是不是也可以用一个函数表示，只要有符合的 i 直接代入即可

f：前缀和数组 → f[i] 表示：[0，i-1] 区间所有元素的和
g：后缀和数组 → g[i] 表示：[i+1，n-1] 区间所有元素的和

所以根据一维前缀和模版的公式可得 f[i] = f[i - 1] + nums[i - 1] 、g[i] = g[i + 1] + nums[i + 1]，注意这个后缀和是从后往前加推导的

💻第二步：

接着遍历题目的数组，枚举出符合 f[i] == g[i] 情况的下标就行了

💻细节问题：

根据我们写的两个公式，当 i = 0 ，i = n - 1 时，即第一个数和最后一个数的下标，发现会出现 f[-1] 、g[n] 的情况，也就是数组越界，所以前缀和要从第二个数开始，后缀和要从倒数第二个数开始，那么第一个数和最后一个数会不会访问不到？答案是不会的，后缀和会访问到第一个数，前缀和会访问到最后一个数。因此当 i 在最左侧或最右侧时，令 f[0] 为 0 ，g[n-1] 为 0 来处理这种特殊情况

💻代码实现:

#include <vector>
#include <iostream>
using namespace std;

class Solution 
{
public:
    int pivotIndex(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n), g(n);

        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];
        }
        for (int i = 0; i < n; ++i)
        {
            if (f[i] == g[i])
            {
                return i;
            }
        }
        return -1;
    }
};

如果数组存在中心下标，返回 1 ；不存在中心下标，返回 -1

1.2 除自身以外数组的乘积

✏️题目描述：

✏️示例：

传送门：除自身以外数组的乘积

题解:
💻细节问题：
本题和寻找数组的中心下标思路基本一致，因为要相乘，所以令 f[0] = 1，g[n-1] = 1，要额外创建一个数组存放各个位置下乘积的结果

💻代码实现:

#include <vector>
#include <iostream>
using namespace std;

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        //1.读取数据
        int n = nums.size();
        vector<int> f(n), g(n);
        //2.预处理前缀积和后缀积
        f[0] = g[n - 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];
        }
        //3.使用
        vector<int> ret(n);
        for (int i = 0; i < n; ++i)
        {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
};

2.前缀和+哈希表

2.1 和为k的子数组

✏️题目描述：

✏️示例：

传送门：和为k的子数组

题解:
💻第一步：

根据题意要求和为k的子数组，那么假设在某个下标为 i 处有符合题意的子数组，前缀和为 sum 表示

那么就有 sum[i] - sum[j] = k ，移项可得 sum[i] - k = sum[j] ，所以要求和为 k 的子数组等同于在不断往前求前缀和 sum[i] 的过程中，计算 sum[i] - k 能否找到符合题意的 sum[j]

💻第二步：

因为前缀和可能存在重复的情况，我们又需要计算前缀和其对饮出现的次数，进而我们可以想到哈希表来处理这种情况

💻细节问题：

🚩前缀和加入哈希表的时机？

在不断往前求前缀和 sum[i] 的过程中，i 是不断变化的，我们是要找在 [0，i-1] 区间内，有多少个前缀和等于 sum[i] - k ，我们关心的是 sum[i]-k 是否在之前出现过，以及出现的次数，这样就能知道有多少个子数组的和为 k

• 如果一次性把每个位置的前缀和都放入哈希表，会导致一些问题。例如，当有一个数组nums = [1,2,3]，k = 3

• 假设我们在遍历过程中，不加判断地每次都放入哈希表。当第一次计算到前缀和为3（1 + 2）时放入哈希表，然后继续遍历到3这个元素时，前缀和变成了6，如果此时又放入哈希表，就会覆盖之前前缀和为3的记录

• 但是，从1开始到2的子数组和为3，从3本身这个元素也构成和为3的子数组，这两个情况是不同的，如果错误地覆盖了之前的记录，就无法正确统计出和为k的子数组数量

🚩不用真的创建一个前缀和数组

用一个变量sum来标记前一个位置的前缀和即可

🚩如果整个前缀和等于k呢？

那么就每次遍历开始前特殊的令 hash[0] = 1

💻代码实现:

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

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;
    }
};

2.2 和可被k整除的子数组

✏️题目描述：

✏️示例：

传送门：和可被k整除的子数组

题解:
💻细节问题：

本题基本上与和为k的子数组思路一致

补充两个知识点：

1. 同余定理
   
2. 负数结果修正成正数

因为数组里可能会存在负数，而数组下标没有负数，所以需要修正

所以根据同余定理，这里本质上就是在求在[0，i-1]区间内，有多少个前缀和的余数等于 sum % k

💻代码实现:

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        unordered_map<int, int> hash;
        hash[0 % k] = 1;

        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;
    }
};

2.3 连续数组

✏️题目描述：

✏️示例：

传送门：连续数组

题解:
💻细节问题：

该题的思路也是前缀和+哈希表，要求和为有相同数量的 0 和 1，不妨令所有的 0 为 -1，也就把题目转化为 sum[i] - sum[j] = 0，即 sum[i] = sum[j]，求在遍历前缀和的过程中能不能找到前面的一个前缀和与其相等，注意 hash[0] = -1

如果在后面又求到一个符合sum[i] = sum[j]的怎么办？

本题求的是最长连续子数组，所以两个是同种情况，无需考虑覆不覆盖的问题，无论哪个都可以

💻代码实现:

#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;

class Solution 
{
public:
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int, int> hash;
        hash[0] = -1;
        
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i] == 0 ? -1 : 1;
            if (hash.count(sum))
            {
                ret = max(ret, i - hash[sum]);
            }
            else
            {
                hash[sum] = i;
            }
        }
        return ret;
    }
};

3.二维前缀和拓展

3.1 矩阵区域和

✏️题目描述：

✏️示例：

传送门：矩阵区域和

💻解读题意：

这题单看题目或许有点难理解，以示例 1 为例，每个方格里的数对应的求和矩阵，为该方格周围延伸 k 长度所围成的数字加和（若超出范围外，则数组外的不算）。比如 2 的矩阵求和为 1 + 2 + 3 + 4 + 5 + 6 = 21，5 的矩阵求和为 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45，求和包括原本的数

💻第一步：

本题是二维前缀和模版的延伸，所以要用到上一篇的两个公式

传送门：【模版】前缀和（二维）

根据题意我们可以延伸该方格周围 k 长度，若超出范围，则让他回到边界上，使用 max 和 min 就能解决

💻第二步：

这也是最重要的一步，因为 dp 的下标是从 1 开始读入数据，mat 和 ans 的下标是从 0 开始读入数据的， 为了能使用同一个公式表示来计算，就需要进行函数映射的操作

映射关系如图所示

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int m = mat.size(), n = mat[0].size();
        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][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        vector<vector<int>> ans(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;
                ans[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ans;
    }
};

以上就是所有精选的前缀和算法题解析，多写几遍代码，不要死套模版，灵活理解应用能够更好地掌握前缀和算法，整理不易，如有出错希望能够私信博主指出错误！😎

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！