给定一个整数数组和一个整数 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(n 3)。
2、穷举优化-去除重复计算
上述方法中对每个子串进行求和时，都是从头至尾进行累加计算，存在大量的重复计算。因为在第二层的循环结束时已经得到了[i,j]的和，下次循环求[i,j+1]时则没必要再次从头到尾计算，直接上次的和加上nums[j+1]即可，时间复杂度为
O(n 2)。
//穷举所有子串[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(n 2)。
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;
}
};前缀和算法
前缀和是一个数组的某项下标之前(包括该元素)的所有数组元素的和，前缀和是一种重要的预处理操作，可以降低查询的时间复杂度。
1、一维前缀和
一维前缀和主要用于使用O(1)的时间，计算出区间和：nums[i]+nums[i+1]+…+nums[j]
2、二维前缀和
二维前缀和主要用于对一个矩阵，在O(1)的时间内计算出子矩阵的和。
声明：本站稿件凡恩品牌资讯以外部分类目资讯转载来自于互联网，如有疑义请联系我们删除。
