当前位置 博文首页 > 谢蟹蟹猴啊的博客：Leetcode560：和为K的子数组
题目：
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
思路：
这个题目是Leetcode1074:元素和为目标值的子矩阵数量的简化版。之前的题目是二维数组求和子集，现在变成了一维数组求子集。相当于略去了对上下边界的遍历，只对左右进行遍历搜索。
方法1： 就是上述思路展开的代码，前缀和+哈希表，基本和Leetcode1074的哈希表子部分一致。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int len=nums.size();
vector<int>sum(len+1);
unordered_map<int,int>map;
int count=0;
map[0]=1; //很关键！
for(int i=1;i<=len;i++){
sum[i]=sum[i-1]+nums[i-1];
if(map.find(sum[i]-k)!=map.end())
count+=map[sum[i]-k]; //也就是说这个操作只对当前sum之前的元素进行检索。到它为止的检索依靠mp[0]=1；
//上面的操作是看当前的sum之前是否存在一个结点，让这个结点到sum当前等于k！有的话就看看这个结点个数
//结束之后就放入这个结点。原因在上面说了，单个结点是不是解可以判断，到这个结点为止是的话就是0，前面初始化也给出了。
map[sum[i]]++; //这个一定要最后入哈希表，因为前面的计数中假设K=0，那每次都要+1了
}
return count;
}
};
对代码简化下就是：
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1;
int count = 0, pre = 0;
for (auto& x:nums) {
pre += x;
if (mp.find(pre - k) != mp.end()) {
count += mp[pre - k];
}
mp[pre]++;
}
return count;
}
};
方法2： 枚举的思路，考虑以 ii结尾和为 kk的连续子数组个数，我们需要统计符合条件的下标 j 的个数。sum用来记录每次以i结尾的情况下，往前面走的子集之和，反正是递增的嘛~
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int count = 0;
for (int start = 0; start < nums.size(); ++start) {
int sum = 0;
for (int end = start; end >= 0; --end) {
sum += nums[end];
if (sum == k) {
count++;
}
}
}
return count;
}
};
这里顺便附上两数之和的代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]); //如果在哈希表中找到当前元素互补项就返回哈希表下标
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
