【算法】前缀和例题讲解

例一：

724. 寻找数组的中心下标

思路：

典型的前缀和题目，我们只需要创建前缀和数组和后缀和数组，然后一一寻找两者相等的下标即可。

代码：

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

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

思路：

本题跟第一题的思路基本一样，只不过把和改成乘积，依然用前缀思想即可。

代码：

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector <int> f(n,1),g(n,1),ans(n);//分别计算前缀乘积和后缀乘积for(int i = 1;i<n;i++)f[i] = f[i-1] * nums[i-1];for(int i = n-2;i>-1;i--)g[i] = g[i+1] * nums[i+1];for(int i = 0;i<n;i++)  ans[i] = f[i] * g[i];return ans;}
};

例3：560. 和为 K 的子数组

思路：前缀和 + 哈希表

本题比较前面的题有难度，我们首先要引入一个概念，在动态规划中，以i位置为结尾的所有子数组。

这样肯定是能列举所有的情况。

假定以i位置为结尾的子数组的值就是k，那么前面的数组和就是sum-k,因此我们就要在前面利用前缀和去寻找值为sum-k。

细节问题：

1. 在计算i位置之前，哈希表里面只保存【0，i-1】位置的前缀和
2. 不用真的创建一个前缀和数组，用一个变量sum来标记前一个位置的前缀和即可
3. 如果整个前缀和等于k呢？hash[0] = 1;

代码：

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;//<前缀和,前缀和出现次数>//特殊情况，sum直接等于khash[0] = 1;int sum = 0;int num = 0;//记录出现的次数for(int i = 0;i<nums.size();i++){sum += nums[i];if(hash.count(sum - k))num += hash[sum - k];hash[sum]++;}return num;}};

例4：