Clean 16ms C++ Solution


  • 17
    W

    The keys are the elements in nums and the values are their indices (1-based). Since we are guaranteed with one and only one solution, don't worry about overriding indices.

    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        vector<int> res(2, 0);
        for (int i = 0; i < nums.size(); i++) {
            if (hash.find(target - nums[i]) != hash.end()) {
                res[0] = hash[target - nums[i]], res[1] = i + 1;
                return res;
            }
            hash[nums[i]] = i + 1;
        }
    }

  • 1
    N

    This code assumes that the element of "nums" is different. So it may not work if nums = {0, 2, 4, 0} with target = 0.


  • 0
    W

    It actually works. You will put the first 0 in the hash table, and when you come to the second one, you say 'Great! There is a 0 in the hash table so that 0 + 0 = 0', and you will output them. Try running the code over the test case.


  • 0
    V

    What does comma here mean (hash[target - nums[i]], res[1] )?


  • 0
    W

    This line is equivalent to the following two lines:

    res[0] = hash[target - nums[i]];

    res[1] = i + 1;


  • 0

    That's really cool! I hardly used 'find' function before.


  • 0
    M

    How are hashmaps made in c++?
    What header file do i need to use to use f'ind' functions of hash?


  • 0
    W

    C11 has given C++ programmers a lot of gifts :) You only need to include <unordered_map> to use hashmaps (there are also ordered map and other types). Hashmaps in the standard library is built upon binary tree structure. Here is a good place to start: http://www.cplusplus.com/reference/


  • 0
    X

    @malvika123

    #include<unordered_map>//unordered_map(unordered_multimap) uses hash
    

  • 0
    X
    if (hash.find(target - nums[i]) != hash.end())
    

    it can be replaced as

    if (hash(target - nums[i]))
    

  • 0
    I

    @xiaonimo said in Clean 16ms C++ Solution:

    if (hash.find(target - nums[i]) != hash.end())
    

    it can be replaced as

    if (hash(target - nums[i]))
    

    They are not equivalent, see: http://www.cplusplus.com/reference/map/map/operator[]/


  • 0
    W

    With two same keys, will the second replace the first like the usual map do & How does unordered_map judge it reaches hash.end() when meeting some elements in collision?


  • 0
    V

    @wz2326 use iterator->second (iterator is returned by hash.find) instead of hash[...] to avoid extra hash lookup.


  • 0
    A

    The solution is clean and efficient. But it is still not O(n) as unordered_map has worst case complexity as O(size of map).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.