本文主要记录前缀和的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。前缀和是LeetCode中的一种解题技巧，其本质就是数组里的前n项和。我们一般通过一个前缀和数组来保存数组中前n位的和。前缀和的作用就是可以帮助我们快速求解数组中每个小区间的和，例如我们要求nums[2]到nums[4]的和，只需要求presum[5]-presum[3]即可。前缀和数组的获取也非常简单，如下：
vector<int> presum(n+1,0);
for(int i=0;i<n;++i) presum[i+1]=presum[i]+nums[i];
一、子串/子序列/子数组
1、寻找中心索引
724. 寻找数组的中心下标（简单难度）
剑指 Offer II 012. 左右两边子数组的和相等（简单难度）
1991. 找到数组的中间位置（简单难度）
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int res = 0;// 结果，连续子数组的个数
// 初始化哈希表
unordered_map<int, int> dict; // <前缀和,次数>
dict[0] = 1;//
// 遍历计算前缀和
int preSum = 0;// 前缀和
for (int num:nums) {
preSum += num;
// 哈希表中存在
if (dict.count(preSum - k) >0) {
res += dict[preSum - k];
}
// 哈希表中不存在，则新建
++dict[preSum];
}
return res;
}
};
2、和为k的连续子数组
560. 和为 K 的子数组（中等难度）
剑指 Offer II 010. 和为 k 的子数组（中等难度）
930. 和相同的二元子数组（中等难度）
一、双重遍历（会超时）
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len=nums.size();
int res = 0;// 结果，连续子数组的个数
int sum=0;
// i负责连续子数组的起点索引
for(int i=0;i<len;++i){
// j负责连续子数组的终点索引
for(int j=i;j<len;++j){
sum+=nums[j];
if(sum==k){
res++;
}
}
sum=0;//起点变动，重新计和
}
return res;
}
};
二、前缀和+双重遍历（会超时）
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len=nums.size();
int res = 0;// 结果，连续子数组的个数
// 计算前缀和
vector<int> presum(nums.size()+1,0);//前缀和数组大小是nums的大小+1
for(int i=0;i<nums.size();++i){
presum[i+1]=presum[i]+nums[i];
}
// i负责连续子数组的起点索引
for(int i=0;i<len;++i){
// j负责连续子数组的终点索引
for(int j=i;j<len;++j){
if(presum[j+1]-presum[i]==k){
res++;
}
}
}
return res;
}
};
三、前缀和+哈希表
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int res = 0;// 结果，连续子数组的个数
// 初始化哈希表
unordered_map<int, int> dict; // <0-i的前缀和,出现次数>
//dict[0] = 1;//presum==k的情况
// presum-k的出现次数和presum的出现次数是一样的（两数之和的原理）
int presum = 0;// 前缀和
for(int num:nums){
presum+=num;
// 如果presum==k，结果+1
if(presum==k)
res += 1;
// 如果presum-k在哈希表中存在，结果+其起初
if (dict.count(presum - k) >0) {
res += dict[presum - k];
}
// 将presum加入哈希表
dict[presum]++;
}
return res;
}
};
1248. 统计「优美子数组」
class Solution {
public:
int numberOfSubarrays(vector<int>& nums, int k) {
int res=0;
// 初始化哈希表
unordered_map<int,int> dict;//<[0,i]的奇数个数，出现次数>
dict[0] = 1;
// 遍历数组
int oddnum=0;// [0,i]的奇数个数
for(int num:nums){
oddnum+=num & 1;//num&1==1表示奇数，num&1==0表示偶数
// 哈希表中已存在，则加入结果
if(dict.count(oddnum-k)>0){
res+=dict[oddnum-k];
}
//更新哈希表中的结果
dict[oddnum]++;
}
return res;
}
};
974. 和可被 K 整除的子数组（中等难度）
class Solution {
/*
因为有如下公式((a*K+c)-(b*K+c)) % K = 0一定成立。
所以，每次只需要在字典中保存当前子数组的和除以K取余数的结果出现的次数即可,
然后每次查询最新子数组除以K取余数的结果在字典中已经出现的次数,
这个就是可以目前新增的可以构建出和可被K整除的子数组数量。
*/
public:
int subarraysDivByK(vector<int>& nums, int k) {
int res = 0;// 结果，连续子数组的个数
// 初始化哈希表
unordered_map<int, int> dict; // <前缀和,次数>
dict[0] = 1;//
// presum-k的个数和presum的个数是一样的（两数之和的原理）
int presum = 0;// 前缀和
for(int num:nums){
presum+=num;
int key=(presum%k+k)%k;//presum%k的余数，负数为 (余数 + K) % K
// 哈希表中存在该key，添加key
if (dict.count(key) >0) {
res += dict[key];
}
// 哈希表中的key频率+1
++dict[key];
}
return res;
}
};
523. 连续的子数组和（中等题目）
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
// 初始化哈希表
unordered_map<int, int> dict; // <前缀和,最小索引>
dict[0] = -1;//
// presum-k的个数和presum的个数是一样的（两数之和的原理）
int presum = 0;// 前缀和
for(int i=0;i<nums.size();++i){
presum+=nums[i];
int key=presum%k;//presum%k的余数，负数为 (余数 + K) % K
// 哈希表中存在该key，说明之前已经存在被key整数的数
if (dict.count(key) >0) {
if(i-dict[key]>=2){
return true;
}
}
// 哈希表中不存在该key时，说明之前不存在满足题意的数，
else{
dict[key]=i;//最小索引
}
}
return false;
}
};