主要参考：
一套模板解决四个《前缀和+哈希表》问题
动画模拟】秒杀七道题
- 前缀和
- leetcode部分题目
- [560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/)
- 1.两数之和
- [724. 寻找数组的中心下标](https://leetcode.cn/problems/find-pivot-index/)
- [1248. 统计「优美子数组」](https://leetcode.cn/problems/count-number-of-nice-subarrays/)
- [974 和可被 K 整除的子数组](https://leetcode.cn/problems/subarray-sums-divisible-by-k/)
首先明确：
子序列：可以连续，也可以不连续
子数组（子字符串）：必须是连续的
前缀和思想和滑动窗口会经常用在求子数组和子串问题上
前缀和。
前缀和其实和求解数列的和十分相似
Sn = a1+a2+a3+…an; 此时Sn就是数列的前 n 项和。
例 S5 = a1 + a2 + a3 + a4 + a5; S2 = a1 + a2。
故可以通过 S5-S2 得到 a3+a4+a5 的值。
这个过程就和我们做题用到的前缀和思想类似。
前缀和数组里保存的就是前 n 项的和。
通过前缀和数组保存前 n 位的和，
presum[1]保存的就是 nums 数组中前 1 位的和，也就是 presum[1] = nums[0],
presum[2] = nums[0] + nums[1] = presum[1] + nums[1]. 依次类推，
则可以通过前缀和数组可以轻松得到每个区间的和。
for (int i = 0; i < nums.size(); i++) {
presum[i+1] = nums[i] + presum[i];
}
leetcode部分题目
560. 和为 K 的子数组
前缀和：（超时）
class Solution {
public:
int subarraySum(vector& nums, int k) {
int n=nums.size();
vector presum(n+1);
int ans=0;
for(int i=0;i
//前缀和是presum[1]开始填充的
presum[i+1]=nums[i]+presum[i];
}
for(int i=0;i
for(int j=i;j
//注意偏移，因为我们的nums[2]到nums[4]等于presum[5]-presum[2]
//所以这样就可以得到nums[i,j]区间内的和
if(presum[j+1]-presum[i]==k){
ans++;
}
}
}
return ans;
}
};
前缀和+哈希表：
class Solution {
public:
int subarraySum(vector& nums, int k) {
unordered_map map={{0,1}}; //初始值根据题意进行改变
int ans=0,presum=0;
for(auto& num:nums){
presum+=num;
int cur=presum-k; //cur值根据题意进行改变
if(map.count(cur)){
ans+=map[cur];
}
map[presum]++; //map[cur或者presum]根据题意改变
}
return ans;
}
};
1.两数之和
思路：
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x
使用暴力发枚举寻找 target - x 的时间复杂度过高
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)。
创建一个哈希表，对于每一个 x，
首先查询哈希表中是否存在 target - x，
然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配
class Solution {
public:
vector twoSum(vector& nums, int target) {
int n=nums.size();
unordered_map mp;
for(int i=0;i
if(mp.count(target-nums[i])){
return {{i,mp[target-nums[i]]}};
}
mp[nums[i]]=i;
}
return {};
}
};
724. 寻找数组的中心下标
思路：
求出前缀和数组，
计算每个下标前面及后面的值 ，比较是否相等，若相等，则是中心坐标。
class Solution {
public:
int pivotIndex(vector& nums) {
int n=nums.size();
vector presum(n+1);
presum[0]=0;
for(int i=0;i
presum[i+1]=presum[i]+nums[i];
}
for(int i=1;i<=n;i++){
int pre=presum[i-1];
int back=presum[n]-presum[i];
if(pre==back){
return i-1;
}
}
return -1;
}
};
1248. 统计「优美子数组」
思路：
与 求和为 K 的子数组 相似，这个题目是让求 恰好有 k 个奇数数字的连续子数组，这两个题几乎是一样的，
上个题中将前缀区间的和保存到哈希表中，
这个题目只需将前缀区间的奇数个数保存到区间内即可，
只不过将 sum += x 改成了判断奇偶的语句。
前缀和：超时
class Solution {
public:
int numberOfSubarrays(vector& nums, int k) {
int n=nums.size();
vector sum(n+1);
int ans=0;
sum[0]=1;
for(int i=0;i
//前缀和是sum[1]开始填充的
sum[i+1]=sum[i]+(nums[i]&1);
}
for(int i=0;i
for(int j=i;j
//注意偏移，因为我们的nums[2]到nums[4]等于sum[5]-sum[2]
//所以这样就可以得到nums[i,j]区间内的和
if(sum[j+1]-sum[i]==k){
ans++;
}
}
}
return ans;
}
};
前缀和+哈希表：
class Solution {
public:
int numberOfSubarrays(vector& nums, int k) {
unordered_map map={{0,1}};
int sum=0;//统计奇数的个数
int ans=0;
for(auto& a:nums){
sum+=(a&1);//如果是奇数则加一，偶数加0，相当于没加
int cur=sum-k;
if( map.count(cur)){
ans+=map[cur];
}
map[sum]++;
}
return ans;
}
};
974 和可被 K 整除的子数组
思路：
与 560. 和为 K 的子数组 一模一样 ，最后判断条件换一下即可。
前缀和：超时
class Solution {
public:
int subarraysDivByK(vector& nums, int k) {
int n=nums.size();
vector presum(n+1);
int ans=0;
for(int i=0;i
//前缀和是presum[1]开始填充的
presum[i+1]=nums[i]+presum[i];
// cout<
}
for(int i=0;i
for(int j=i;j
//注意偏移，因为我们的nums[2]到nums[4]等于presum[5]-presum[2]
//所以这样就可以得到nums[i,j]区间内的和
if((presum[j+1]-presum[i])%k==0){
ans++;
}
}
}
return ans;
}
};
前缀和+哈希表：
class Solution {
public:
int subarraysDivByK(vector& nums, int k) {
unordered_map map={{0,1}}; //初始值根据题意进行改变
int ans=0,sum=0;
for(auto& a:nums){
sum+=a;
int cur=(sum%k+k)%k;
if(map.count(cur)){
ans+=map[cur];
}
map[cur]++;
}
return ans;
}
};
523 连续的子数组和
930.和相同的二元子数组（中等)
