《信息学C++知识讲解》：前缀和算法总结(一)

浏览量: 96

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

来源：力扣（LeetCode）第560道题

1、暴力穷举
可以对所有的子数组进行穷举，然后分别求和，和等于k则计数加1。

//穷举所有子串[i,j]int countK = 0;for(int i = 0;i< nums.size();i++)//穷举所有以i开头的子串{    for(int j = i;j < nums.size();j++)//穷举所有子以j结尾的子串    {        int sum = 0;        for(int k = i;k <= j;k++)//对子串求和        {            sum += nums[k];        }        if( sum == k)//判断和是否为k            countk++;    }}

枚举所有的子串开头 i 和结尾 j，然后确定起始位置后对子串进行从头到尾求和，时间复杂度为O(n3)。

2、穷举优化-去除重复计算
上述方法中对每个子串进行求和时，都是从头至尾进行累加计算，存在大量的重复计算。因为在第二层的循环结束时已经得到了[i,j]的和，下次循环求[i,j+1]时则没必要再次从头到尾计算，直接上次的和加上nums[j+1]即可，时间复杂度为O(n2)。

//穷举所有子串[i,j]int countK = 0;for(int i = 0;i< nums.size();i++)//穷举所有以i开头的子串{    int sum = 0;    for(int j = i;j < nums.size();j++)//穷举所有子以j结尾的子串    {        sum += nums[j];//上次和的基础上加当前值即可        if( sum == k)//判断和是否为k            countk++;    }}

3、使用前缀和
上述方法中计算[i,j+1]的和时，直接用[i,j]的和加上nums[j+1]，减少了子串再次从头到尾的计算，根据这一思路，我们定义数组 pre[i] 为[0..i]里所有元素的和：那么 pre[i] = pre[i-1]+nums[i] 。那么要计算任意子区间[i,j]的和，通过pre[j]-pre[i]即可得到。

int size = nums.size();//数组长度vector<int> pre = vector(size,0);//记录[0,i]每个位置的和//构造前缀和for(int i = 1;i< nums.size();i++){    pre[i] = pre[i-1]+nums[i];}//穷举所有子数组int countK = 0;for(int i = 0;i< nums.size();i++)//穷举所有以i开头的子串{    for(int j = i;j < nums.size();j++)//穷举所有子以j结尾的子串    {        if( pre[j] - pre[i] == k)            countK++;    }}

pre数组作为对数据的预处理只执行一次即可，当我们需要返回任意子数组[i,j]的和时，可以通过 pre[j] – pre[i] O(1) 用的时间得到。但对本题来说，依然需要对数组进行两层遍历，时间复杂度为O(n2)。

4、哈希表优化

在上述方法中，第二次for循环的作用是：计算有几个 j 能够使 pre[j] 和 pre[i] 的差等于k。但实际上我们不关心前缀和对应哪几项，只需要知道有几个前缀和满足条件即可。因此我们可以用哈希表记录前缀和及该和出现的次数，就可以用O(1)的时间做出判断。

哈希表中键值对，键：从0到当前项的总和、值：这个前缀和出现了几次，初始化前缀和为0出现了1次。

class Solution {public:    int subarraySum(vector<int>& nums, int k) {        unordered_map<int,int> mp;//记录 前缀和-次数        mp[0] = 1;//初始化0出现了一次        int count = 0,pre = 0;//仅需要记录前一个值即可，不需要用数组记录所有的前缀和        for(int i =0;i < nums.size();i++)        {            pre+=nums[i];//计算前缀和            if(mp.find(pre-k) != mp.end() )//前面结果中存在满足条件的前缀和            {                count+=mp[pre-k];            }            mp[pre]++;//相同的前缀和次数加1        }        return count;    }};