大一计算机的自学总结：前缀和

前言

作为一种基础算法，前缀和以及构建前缀信息的思想是非常非常重要的。

一、内容

前缀和的内容很简单，就是求数组从0到i-1位置上数值的累加和。经常被用来解决子数组的相关问题，还会在一些更复杂的问题上用来维护前缀信息。

二、相关题目

1.区域和检索 - 数组不可变

class NumArray {
public:vector<int>sum;NumArray(vector<int>& nums) {sum.resize(nums.size()+1);for(int i=1;i<=nums.size();i++){sum[i]=sum[i-1]+nums[i-1];//构建前缀和数组}}int sumRange(int left, int right) {return sum[right+1]-sum[left];}
};

这个题就是最基础的前缀和，即构建前缀和数组。

要求某区间子数组的累加和，只需让right+1位置的前缀和减去left位置的前缀和即可。

2.未排序数组中累加和为给定值的最长子数组长度

#include <bits/stdc++.h>
using namespace std;int main()
{int n,k;cin>>n>>k;vector<int>nums(n);map<int,int>mp;//构建前缀和最早出现位置mp[0]=-1;//初始化int ans=0;for(int i=0,sum=0;i<n;i++){cin>>nums[i];sum+=nums[i];map<int,int>::iterator iter=mp.find(sum-k);if(iter!=mp.end()){ans=max(ans,i-mp[sum-k]);}iter=mp.find(sum);if(iter==mp.end()){mp[sum]=i;}}cout<<ans;
}

这个题就是很经典的构建前缀和最早出现位置，用于解决最长子数组问题。

思路和上题类似，若目标值为k，0~i位置累加和为sum，则只需找累加和为sum-k最早出现的位置即可。

注意，初始化前缀和为0时数组下标为-1，这很重要！！！

3.和为 K 的子数组

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans=0;map<int,int>cnt;//记录前缀和出现次数cnt[0]=1;for(int i=0,sum=0;i<nums.size();i++){sum+=nums[i];map<int,int>::iterator iter=cnt.find(sum-k);if(iter!=cnt.end()){ans+=cnt[sum-k];}cnt[sum]++;}return ans;}
};

这个题需要构建前缀和的出现次数，剩下的思路和前两题类似，每次让ans加上出现次数即可。

4.未排序数组中累加和为给定值的最长子数组系列问题补1

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;vector<int>nums(n,0);//与数值无关，只关心正负的个数 -> 找前缀和为0for(int i=0,num;i<n;i++){cin>>num;if(num>0){nums[i]=1;}else if(num<0){nums[i]=-1;}}map<int,int>len;len[0]=-1;int ans=0;for(int i=0,sum=0;i<n;i++){sum+=nums[i];map<int,int>::iterator iter=len.find(sum);if(iter!=len.end()){ans=max(ans,i-len[sum]);}else{len[sum]=i;}}cout<<ans;
}

这个题就需要转化一下了。

因为只和正负数的数量有关，和数值大小无关，所以考虑将正数设为1，负数设为-1，这样当前缀和为0时，正负数的数量相同。

5.表现良好的最长时间段

class Solution {
public:int longestWPI(vector<int>& hours) {vector<int>nums(hours.size());for(int i=0;i<hours.size();i++){nums[i]=hours[i]>8?1:-1;}int ans=0;map<int,int>len;len[0]=-1;for(int i=0,sum=0;i<nums.size();i++){sum+=nums[i];if(sum>0){ans=max(ans,i+1);}else{map<int,int>::iterator iter=len.find(sum-1);if(iter!=len.end()){ans=max(ans,i-len[sum-1]);}iter=len.find(sum);if(iter==len.end()){len[sum]=i;}}}return ans;}
};

这个题的转化思路和上个题一样，同样是只关心是否大于八小时，所以转化成1和-1。

之后若sum大于0，说明此时大于八小时天数多，就直接结算；否则，需要找累加和大于0的子数组，即之前累加和小于sum的最早位置，而对于需要找的这个累加和，就需要一点思考了。

先观察数组里数的特征，发现只有1和-1两个数且初始的sum等于0。假如此时的sum=-4，说明肯定是从0一直减到-4的，所以，只需要去找累加和-4-1=-5最早出现的位置即可。不找更小的数的原因是，假如找-6，因为sum是从0一直减到-6的，所以-6之前必定出现过一次-5，使得子数组可以变得更长。由此一直递推，可以得出，只需要找sum-1最早出现的位置即可。

最后的这个思路还挺不好想的说实话……

6.使数组和能被 P 整除

class Solution {
public:int minSubarray(vector<int>& nums, int p) {//求整体余数int r=0;for(int i=0;i<nums.size();i++){r=(r+nums[i])%p;//加法同余}//使删除部分余数=整体余数int ans=INT_MAX;map<int,int>late;late[0]=-1;for(int i=0,sum=0,need;i<nums.size();i++){sum=(sum+nums[i])%p;late[sum]=i;//先加入need=(sum-r+p)%p;//减法同余map<int,int>::iterator iter=late.find(need);if(iter!=late.end()){ans=min(ans,i-late[need]);}}return ans==nums.size()?-1:ans;//注意特判}
};

这个题需要构建前缀和余数。

整体思路是，先求出数组整体的余数。根据减法的同余原理，若要求删除后余数为0，则要删除累加和余数也为整体余数的子数组。而当0~i位置累加和余数为sum时，需要找sum减去整体余数的最晚出现位置，即删除长度最短。

7.每个元音包含偶数次的最长子字符串

class Solution {
public:int findTheLongestSubstring(string s) {int ans=0;vector<int>map(32,-2);map[0]=-1;for(int i=0,n,status=0;i<s.length();i++){n=num(s[i]);if(n!=-1)//元音{status^=(1<<n);}if(map[status]!=-2)//没出现过{ans=max(ans,i-map[status]);} else{map[status]=i;}}return ans;}int num(char c){if(c=='a'){return 0;}else if(c=='e'){return 1;}else if(c=='i'){return 2;}else if(c=='o'){return 3;}else if(c=='u'){return 4;}return -1;}
};

这个题就需要构建前缀和奇偶状态。

整体思路是，若某几个元音字母数量为奇数，只需要找元音字母状态与此时相同的最早出现位置即可，因为奇+奇=偶，偶＋偶=偶。

再进行思考，可以将五个元音字母的状态用位信息来表示，0为偶数，1为奇数。

再观察发现，这样一共只有2^5=32中状态，所以准备长度为32的数组即可。