算法练习——前缀和

前言：前缀和分为 一维前缀和 、二位前缀和，但无论是一维还是二维，其核心都是先将所有结果存入到另一个数据结构中(注意选用合适的方法，不要暴力求解)，然后再根据题目要求，根据先前存储的值之间的相应关系来求得最终结果。

注：这里更多用到是数学思维。

一：【模板】一维前缀和

题目要求：

解题思路：

给你一个数组，目标是求出对应下标之间的和，按照先前所说的先得到所有结果，即求出 0~1、0~2、0~n-1所有数据的和并存入到一块新的空间中，以下图为例，原数组为：

按照上述想法，计算 前n个和，并分别存入到新的空间中，如下图所示：

当我们想得到任意两个下标之间的和时，只需要计算 dp[右端下标] - dp[左端下标-1]即可得到答案

思考1：如何优化求dp的算法？

答：是暴力求解吗？那肯定不是！想想暴力求解的过程中什么东西被重复计算了？

比如此时你求出了 前n-1个和，并存放到了 dp[n-1] 处，当你要求 前n个和 时，如果使用暴力解法，那 前n-1个数的和 是不是被重复计算了？那么优化的思路就来了，因为 dp[n-1] 已经保存了 前n-1个数的和，因此只需 dp[n-1] + arr[n] 即可得到 前n个数的和

 即：dp[n] = dp[n-1] + arr[n];

思考2：上述公式 n-1 会出现越界问题，如何解决？

答：创建 n + 1 个大小的空间，并全部初始化为0，同时 dp 中下标为1位置处开始存储，这样即解决了越界问题，又不妨碍最终的计算结果。

实现代码：

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

int main() {
    
    //创建一维数组
    int n = 0;
    int q = 0;
    cin >> n >> q;
    vector<int> arr(n+1);
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    //创建dp
    vector<long long> dp(n+1);
    for(int i = 1; i <= n; i++)
    {
        dp[i] = dp[i-1] + arr[i];
    }

    //计算目标值
    int l = 0;
    int r = 0;
    while(q--)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l-1] << endl;;
    }
    return 0;
}

二：【模板】二维前缀和

题目要求：

解题思路：

同样的思路：需要预先求出一个dp数组(优化算法)，最后通过这个数组来计算最终答案。

此处是一个二维数组，dp中的每一个元素代表的是：从(1,1)位置到该元素位置所构成的矩阵中所有元素的和。

我们将该矩阵划分为四个区域，那么该矩阵所有元素的和为：(A+B)+(A+C)+D-A

 即：dp[i][j] = dp[i][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1];

上述公式中同样存在越界问题，因此二维数组的行和列应都为n+1个大小，并将所有元素置为0。

注：与一维前缀和求dp中每个元素类似，dp[i][j-1]、 dp[i-1][j]、dp[i-1][j-1] 已经保存了上一次的计算结果。单独考虑 dp[1][0] 、dp[0][1]、dp[0][0] 的边界情况时(如下图)，又因为在初始化的过程中，已经多添加了一行一列，且都置为0，因此不影响结果。

现在求以(x1,y1)为左上角,(x2,y2)为右下角构成的矩阵中所有元素的和(即A中所有元素的和)：

如图所示：

dp中：

👉：(x2,y2)处存储的数据是：以(0，0)为左上角，(x2,y2)为右下角矩阵中所有元素的和

👉：(x2,y1-1)处存储的数据是：以(0，0)为左上角，(x2,y1-1)为右下角矩阵中所有元素的和

👉：(x1-1,y2)处存储的数据是：以(0，0)为左上角，(x1-1,y2)为右下角矩阵中所有元素的和

👉：(x1-1,y1-1)处存储的数据是：以(0，0)为左上角，(x1-1,y1-1)为右下角矩阵中所有元素的和

则以(x1,y1)为左上角,(x2,y2)为右下角构成的矩阵中所有元素的和为：

 dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

实现代码：

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

int main() {

    //创建二维数组
    int n = 0; int m = 0; int 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];
        }
    }

    //创建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];
        }
    }

    //计算目标值
    int x1=0;int x2=0;int y1=0;int y2=0;
    while(q--)
    {
        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;
}

三：寻找数组的中心下标

题目要求：

解题思路：

这是一个一维数组，因此使用一维数组前缀和的思路，但是不能死背模板，需要根据不同题目做出改变。

分析：以示例1为例，如图所示：

题目要求某个下标处的 左侧和 = 右侧和(下标处的值不需要考虑) 。

现在设想一个极端情况，下标位于最右侧，那么此时下标位置处的值不需要计算，因此在后续创建dp时，不需要额外创建一个空间。

注：先前需要创建额外空间是因为，原数组中所有值都需要考虑，并且需要额外添加一个0位，而现在数组中有一位不需要考虑，因此不需要多创建空间。

问：那么通过什么方式分别记录左右侧的和呢？

答：左侧的非常好想，这和我们先前做过的一位前缀和一样。

定义一个 vector<long long> front ，如下图：

再定义一个后缀和，后缀和其实和前缀和一样的思路，不过是逆向思维，如图所示：

最后再用for循环遍历，当front[i] == back[i]时，即为目标值。 

注：其实多创建空间也没事，但是在最后遍历的时候可能会比较麻烦，画图也能解决。

实现代码：

    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> front(n);
        for(int i = 1; i<n; i++)
        {
            front[i] = front[i-1] + nums[i-1];
        }

        vector<int> back(n);
        for(int i = n-2; i>=0; i--)
        {
            back[i] = back[i+1] + nums[i+1];
        }
        for(int i = 0; i<n; i++)
        {
            if(front[i] == back[i])
            {
                return i;
            }
        }
        return -1;
    }

四：除自身意外数组的相乘

题目要求：

解题思路：

思路(以示例1为例)：

求出前缀和以及后缀和，两者错位相乘。

实现代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp1(n+1,1);
        vector<int> dp2(n+1,1);
        for(int i = 1; i <= n; i++)
        {
            dp1[i] = dp1[i-1] * nums[i-1];
        }
        for(int i = n - 1; i >= 0; i--) 
        {
            dp2[i] = dp2[i+1] * nums[i];
        }
        vector<int> ret;
        for(int i = 0; i < n; i++)
        {
            ret.push_back(dp1[i]*dp2[i+1]);
        }
        return ret;
    }
};

五：和为k的子数组

题目要求：

解题思路：

思路：前缀和+哈希表辅助

以下图为例：

假设当i遍历到上图位置处，存在子串和为k(黄色框框部分)

那么遍历到i位置之前，需要做的是，将对应0~i每个子串的和加入到hash表中

注：unordered_map<int,int> 第一个参数为sum，第二个参数为该sum出现的次数

那么遍历到图中i位置处时，此时hash中，已经包含了前面所有从0开始子串的和，即蓝线部分。

因为0~i的子串和为sum，目标答案要求和为k，即红线部分，那么现在所需做的就是在蓝线部分找和为sum-k的子串，而hash表中，统计了所有子串的和以及其对应的个数，所以就变成了在hash查找是否存在sum-k，然后再加其对应的个数即可统计个数。

当查找完毕时，再将当前0~i子串的和加入到hash中，以便下一次判断。

细节：如果当前子串0~i刚好满足和为k时，此时hash表中没有统计该值，因此在循环前，应将hash[0] = 1；提前插入hash中。

实现代码：

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& n : nums) {
            sum += n;
            if(hash.count(sum - k)) ret += hash[sum - k];
            hash[sum]++;
        }
        return ret;
    }
};

六：和可被k整除的子数组

题目要求：

解题思路：

思路：本题和上一题思路完全相同。但是！需要提前知道以下两点知识点。

知识点1：同余定理： (a - b)%k = p …… 0  → a%k = b%k； 

知识点2：C++中，负数取余得到的还是负数，为此需要处理负数取余，具体做法为：(n%k+k)%k;对于整数而言，没有变化；对于负数而言，能够将最终答案转为正数，保证了-1，1 对相同的数区域能够得到相同的结果。

本题与上题的区别在于:
1.哈希表中存什么？

答：我们把同于定理改造一下： (sum - 子串)%k = p → sum%k = 子串%k；

其中sum为0~i子串的和，子串为0~i-1中，所有从0开始子串的和，对应上一题中蓝线部分。

那么本题中，我们应该在哈希表中找寻余数为sum%k的数，因此哈希表中存储的数应该为：子串%k

2.判断条件是什么？

答：有了1的认识，判断条件就很简单了，即：哈希表中是否存在余数为sum%k的数

实现代码：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;
        for(auto& n : nums) {
            sum += n;
            if(hash.count((sum%k + k)%k)) ret += hash[(sum%k + k)%k];
            hash[(sum%k + k)%k]++;
        }
        return ret;
    }
};

七：连续数组

题目要求：

解题思路：

思路：觉得陌生？不妨我们将所有的0换成-1试试。这样题目是否就变成了和为0的最长子串？

细节1：hash表存储的数应为：当前子串的和与对应位置i，因为要求最长子串，所以每个和只更新一次！

细节2：若当前0~i子串刚好和为0(假设第一次出现)，而哈希表中没有和为0的值，所以在遍历前，需要将hash[0] = -1，加入到hash表中。

问：为什么不是hash[0] = 1或0？

答：因为本题算最长子串，如果该子串第一次出现，那么其下标i - (-1) 刚好对应子串长度。

以下图为例：

当前i位置处的和为0，hash表中记录和为0对应的值为-1，那么现在长度为i - (-1) = 2;

一般子串长度计算的方式：

和为-1的最靠左的位置为下标0处，下一次和为-1的值位于下标2处，那么当前和为0的子串的长度为 i - hash[-1] = 2 - 0 = 2；

实现代码：

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

八：矩阵区域和

题目要求：

解题思路：

思路(以示例1为例)：本题是二维前缀和，重在对第二题公式的理解，但请不要死记公式。

按照二位前缀和的思路，我们可以求出以下二位前缀和数组dp：

如果要求元素1满足的和，即[0][0]为左上角，[0+1][0+1]为右下角的矩阵每个元素的总和。

那么对应和应为：dp[2][2] - dp[0][2] - dp[2][0] + dp[0][0];

如果要求元素3满足的和，即[0][1]为左上角，[0+1][1+1]为右下角的矩阵每个元素的总和。

那么对应和应为：dp[2][3] - dp[2][1] - dp[0][3] + dp[0][1];

细节1：最终结果的数组(ret)、mat、dp数组的下标不是一一对应的，以mat、ret为标准，那么dp中所有坐标都得+1处理。

细节2：因为题目要求横纵坐标分别从 i-k~i+k 、j-k ~ j+k，那么会出现越界的问题，此时在另外定义坐标x1，y1、x2、y2。

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;

来避免越界的问题。

实现代码：

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 = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j] + mat[i][j];
            }
        }
        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[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];
            }
        }
        return ret;
    }
};