目录
力扣560. 和为 K 的子数组
难度 中等
给你一个整数数组 nums
和一个整数 k
,请你统计并返回 该数组中和为 k
的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1:
输入:nums = [1,1,1], k = 2 输出:2
示例 2:
输入:nums = [1,2,3], k = 3 输出:2
提示:
1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= k <= 10^7
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
}
};
解析代码
使用前缀和的方法解决这个问题,因为需要找到和为k的连续子数组的个数。
通过计算前缀和,可以将问题转化为求解两个前缀和之差等于k的情况。
假设数组的前缀和数组为arr,其中arr[i]表示从数组起始位置到第i个位置的元素之和。
那么对于任意的两个下标i和j(i < j),如果arr[j] - arr[i] = k,即从第i个位置到第j个位置的元素之和等于k,那么说明从第i+1个位置到第j个位置的连续子数组的和为k。 通过遍历数组,计算每个位置的前缀和,并使用一个哈希表来存储每个前缀和出现的次数。
在遍历的过程中,检查是否存在arr[j] - k的前缀和,如果存在,说明从某个位置到当前位置的连续子数组的和为k,将对应的次数累加到结果中。
这样,通过遍历一次数组,就可以统计出和为k的连续子数组的个数,时间复杂度为O(N)。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
// 根据前缀和思想,设一个位置前缀和为sum,sum-前缀和 == k的区间即为所求
// 利用哈希求有多少个 sum-前缀和 == k的区间
int n = nums.size(), sum = 0, ret = 0;;
unordered_map<int, int> hash(n); // 左int存前缀和,右int存前缀和出现次数
hash[0] = 1; // 初始化前缀和为0的次数为1(整个数组等于K的情况)
for(int i = 0; i < n; ++i)
{
sum += nums[i]; // 计算i位置的前缀和
if(hash[sum - k] != 0) // 判断i位置前缀和-k是否存在
{
ret += hash[sum - k];
}
hash[sum]++; // 计算i之前只保存i-1
}
return ret;
}
};