leetcode:two sum,Subarray Sum类的问题 (hash table)
程序员文章站
2022-03-08 16:44:46
...
- Subarray Sum Equals K
https://leetcode.com/problems/subarray-sum-equals-k/description/
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Tips:
1,init res = 0. or
Local variables aren’t initialized unless you do it yourself. What you’re seeing is whatever garbage was on the stack before your method was called.
2, init the summap[0] to 1 to cover the case that: sumsofar = k.
3, hash里面村的是前面sumsofar出现的次数,要寻找的是sumsofar - k,因为目标是:
后面的sumsofar - 前面的sumsofar = k,前面的sunsofar都存在hash里
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int>summap;
int res = 0;
summap[0] = 1;
int sumsofar = 0;
for(auto num : nums)
{
sumsofar += num;
res += summap[sumsofar - k];
summap[sumsofar]++;
}
return res;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>map;
vector<int>res;
for(int i= 0; i < nums.size(); i++)
{
int candi = target - nums[i];
if(map.find(candi) != map.end())
{
res.push_back(map[candi]);
res.push_back(i);
break;
}
map[nums[i]] = i;
}
return res;
}
};
- Continuous Subarray Sum
https://leetcode.com/problems/continuous-subarray-sum/description/
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
这个题更有意思,加了限制条件,
1,at least 2 subarray, 存入一个pre,保证现在的sumsofar和前一个sunsofar中间有个gap。现在的sumsofar这个cycle里要先放到pre里,等下一个cycle才能放到hash里,然后再下一个cycle才能找到。
cornor case: [0,1,0] 0
2,目标是k的整数倍:存入set的是sumsofar % kd结果,如果同样的mod结果已经出现过的话,说明:现在的sumsofar-前面已经有sumsofar一定是k的倍数。
3,只需要输出true or false,所以不需要unordered_map, unordered_set足够了
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_set<int>summap;
int sumsofar = 0;
int pre = 0;
for(auto num : nums)
{
sumsofar += num;
sumsofar = k == 0? sumsofar : sumsofar % k;
if(summap.count(sumsofar))
{
return true;
}
summap.insert(pre);
pre = sumsofar;
}
return false;
}
};