[TOC]

​ 本文主要记录前缀和的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。

一、子串/子序列/子数组的LeetCode题目

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