第二步：使用前缀和数组

发布时间：2025-06-24 18:25:56  作者：北方职教升学中心  阅读量：075

如果下标从0开始，比如，要求下标0-2之间元素之和，按照上面的方法就是求dp[2]-dp[-1]，明显越界了，对于这种情况，还需要单独处理。

#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.预处理出一个前缀和矩阵    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][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1];        }    }    //3.利用前缀和矩阵    int x1 = 0, x2 = 0, y1 = 0, y2 = 0;    while(q--)    {        cin >> x1 >> y1 >> x2 >> y2 ;        cout << dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1] << endl;    }}

题目分析：最开始我们想到的肯定是暴力求解，但是很明显暴力求解的时间复杂度很高，是O(n*m*q)，所以我们再来说一种更好的解法--前缀和，第一步，我们预处理出来一个前缀和矩阵dp，dp[i][j]表示从[1][1]位置到[i][j]位置这段区间里面所有元素的和。2.不用真的创建一个前缀和数组，用一个变量sum来标记前一个位置的前缀和即可。这样直接求解的时间复杂度为O(1)。

class Solution {public:    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)     {        int m = mat.size(), n = mat[0].size();        //1.预处理一个前缀和矩阵        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,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;    }};

题目分析：这道题很明显需要用到二维数组前缀和，首先，我们要预处理得到一个前缀和数组dp，dp元素的求法如下图（先以mat的起始下标为(1,1)为例）：

得到前缀和数组之后，假设我们要求(x1,y1)~(x2,y2)区间元素的和，其算法如下图：

按照题目要得到的矩阵，anwser[i][j]所求的就是[i-k][j-k]~[i+k][j+k]区间元素的和，就可以使用上面求ret的方法，但是i-k、除自身以外数组的乘积、这样就和之前和为k的子数组的做法很像，也是使用前缀和+哈希表。这种暴力解法肯定过不了。3.如果有重复的<sum,i>，如何存？只保留前面的那一对<sum,i>。具体来说，第一步：预处理出来一个前缀和数组dp，其中dp[i]表示[1，i]区间内所有元素的和，dp[0]默认设为0，dp[i]=dp[i-1]+arr[i]。矩阵区域和。2.什么时候存入哈希表？使用完之后，丢进哈希表。5.长度怎么算？i-j。当我们想求[l, r]区间的和时，可以直接用dp[r]-dp[l-1]求解。我们从题目中看到，数组元素下标是从1开始的，下标为0的位置我们默认为0。4.默认的前缀和为0的情况，如何存？hash[0]=-1。和可被K整除的子数组、

有几个细节需要处理：1.前缀和加入哈希表的时机：在计算i位置之前，哈希表里只保存[0,i-1]位置的前缀和。2.C++/JAVA中，负%正 = 负，修正-->(a%p+p)%p，这样得到的结果就是一个正确的正数。具体计算过程如下：

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

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

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

题目分析：对于这道题，如果使用暴力求解，其时间复杂度是O(N2)，所以我们换一种方法，我们使用前缀和的思想，在以i为结尾的所有子数组中找，假设以i为结尾的子数组前缀和是sum[i]，那么就是在[0,i-1]区间中，有多少个前缀和为sum[i]-k。

class Solution {public:    int findMaxLength(vector<int>& nums)     {        unordered_map<int,int> hash;        int sum = 0;        hash[0] = -1; //默认有一个前缀和为0的情况        int 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;    }};

题目分析：这道题如果直接求会比较困难，我们可以转化一下，将所有的0改为-1，问题就转化为在数组中，找出最长的子数组，使子数组中所有元素的和为0。和为K的子数组、其实我们不需要搞出一个前缀和数组sum[i]，而只需有一个变量sum就行，sum是前i个元素的和。i+k、j-k、3.如果整个前缀和等于k呢，其实我们应该在开始时设置hash[0]=1。寻找数组的中心下标、所以，我们要使用前缀和方法解决这个问题。

#include <iostream>#include <vector>using namespace std;int main() {    //1. 读取数据    int n = 0, q = 0;    cin >> n >> q;    vector<int> nums(n+1);    vector<long long> dp(n+1);    for(int i = 1; i<= n ;i++)    {        cin >> nums[i];        //2. 预处理出来一个前缀和数组        dp[i] = dp[i-1] + nums[i];    }    //3.使用前缀和数组    int l = 0,r = 0;    while(q--)    {        cin >> l >> r;        cout << dp[r] - dp[l-1] << endl;    }   return 0; }

题目分析：首先来看暴力解法，题目让我们求l到r的和，我们可以找到l，然后依次往后累加，直到加到r，然后执行q次，所以这种暴力解法的时间复杂度是O(N*q)。

class Solution {public:    int subarraysDivByK(vector<int>& nums, int k)     {        unordered_map<int, int> hash;        int sum = 0;        int reminder = 0;        int ret = 0;        hash[0] = 1; // 0这个数的余数        for(auto e : nums)        {            sum += e;  // 当前位置的前缀和            reminder = (sum % k + k)%k; //修正后的余数            if(hash.count(reminder)) ret += hash[reminder]; //统计结果            hash[reminder]++;        }        return ret;    }};

题目分析：对于这道题，我们先要补充两个知识：1.同余定理，(a-b)/p = k，可以得出a%p=b%p。好了，有了这两个补充知识，剩下的就和上道题几乎一样了。

细节问题：为什么我们的下标要从1开始计数？为了处理边界情况。