当前位置 博文首页 > 读研的小狗子的博客：【LeetCode刷题（中等程度）】560. 和为K的
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：前缀和暴力法。（超时）
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefixSum(n + 1,0);
for(int i = 0;i < n;++i)
{
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int ans = 0;
//穷举所有子数组
for(int i = 1;i <= n;++i)
{
for(int j = 0;j < i;++j)
{
if(prefixSum[i] - prefixSum[j] == k)
{
ans++;
}
}
}
return ans;
}
};
优化版本：
class Solution {
public:
unordered_map<int,int>temp{pair{0,1}};
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
int prefixSum = 0;
int ans = 0;
for(int i = 0;i < n;++i)
{
prefixSum += nums[i];
int sum_another = prefixSum - k;//这就是我们要找的
if(temp.find(sum_another)!=temp.end())
ans += temp[sum_another];
temp[prefixSum]++;//记录该前缀和出现的次数
}
return ans;
}
};
