欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode:two sum,Subarray Sum类的问题 (hash table)

程序员文章站 2022-03-08 16:44:46
...
  1. 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;
    }
};
  1. Two Sum
    https://leetcode.com/problems/two-sum/description/
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;
    }
};
  1. 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;
    }
};
相关标签: hash