优选算法——前缀和

目录

1. 数组的中心下标

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

3. 和为k的子数组 

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

5. 连续数组

6. 矩阵区域和 

---

1. 数组的中心下标

题目链接：724. 寻找数组的中心下标 - 力扣（LeetCode）

题目展示：

题目分析：

这里的思想类似于动态规划，我们需要定义出两个状态表示。 

代码实现：

class Solution {
public:int pivotIndex(vector<int>& nums) {int n=nums.size();vector<int> f(n);auto g=f;f[0]=0;g[n-1]=0;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;}
};

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

题目链接：238. 除自身以外数组的乘积 - 力扣（LeetCode）

题目展示：

 

题目分析：

这里需要强调一点，大家不要去死记硬背前缀和的模板，而是要去理解这种思想；比如本题，其实是前缀积，但是本质上和前缀和的思想是一样的。 

代码实现：

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();vector<int> ret(n);vector<int> f(n);auto g=f;f[0]=1;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];}for(int i=0;i<n;i++){ret[i]=f[i]*g[i];}return ret;}
};

3. 和为k的子数组 

题目链接：560. 和为 K 的子数组 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

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

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

题目链接：974. 和可被 K 整除的子数组 - 力扣（LeetCode）

题目展示：

题目分析：

与上题很类似，但是需要一些补充知识；

代码实现：

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

5. 连续数组

题目链接：525. 连续数组 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

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

6. 矩阵区域和 

题目链接：1314. 矩阵区域和 - 力扣（LeetCode）

题目展示：

题目分析：

代码实现：

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