前缀和

前缀和思想和滑动窗口会经常用在求子数组和子串问题上
前缀和。

前缀和其实和求解数列的和十分相似

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<int>& nums, int k) {
        int n=nums.size();
        vector<int> presum(n+1);
        int ans=0;
        for(int i=0;i<n;i++){
            //前缀和是presum[1]开始填充的
            presum[i+1]=nums[i]+presum[i];
        }
        for(int i=0;i<n;i++){
            for(int j=i;j<n;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<int>& nums, int k) {
        unordered_map<int,int> 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<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        unordered_map<int,int> mp;
        for(int i=0;i<n;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<int>& nums) {
       int n=nums.size();
       vector<int> presum(n+1);
       presum[0]=0;
       for(int i=0;i<n;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<int>& nums, int k) {
        int n=nums.size();
        vector<int> sum(n+1);
        int ans=0;
        sum[0]=1;
        for(int i=0;i<n;i++){
            //前缀和是sum[1]开始填充的
            sum[i+1]=sum[i]+(nums[i]&1);
            
        }
        for(int i=0;i<n;i++){
            for(int j=i;j<n;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<int>& nums, int k) {
        unordered_map<int,int> 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<int>& nums, int k) {
        int n=nums.size();
        vector<int> presum(n+1);
        int ans=0;
        for(int i=0;i<n;i++){
            //前缀和是presum[1]开始填充的
            presum[i+1]=nums[i]+presum[i];
            // cout<<presum[i+1]<<" ";
        }
        for(int i=0;i<n;i++){
            for(int j=i;j<n;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<int>& nums, int k) {
        unordered_map<int,int> 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;
    }
};