O(n) C++ solution in 12 lines!


  • -4
    A

    class Solution {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {

        int m=nums.size();
        vector<int> x;
        unordered_map<int, int> mp;
        
        for(int i=0;i<m;i++)
        {
            mp[nums[i]]=i;
        }
        
        for(int i=0;i<m;i++)
        {
            if(mp.find(target-nums[i])!=mp.end() && i!=mp.find(target-nums[i])->second)
            {
                x.push_back(i+1);
                x.push_back((mp.find(target-nums[i])->second)+1);
        
                return x;
            }
        }
        return x;
    }
    

    };


  • 0
    H

    What if identical numbers exist in the sequence? For example the nums is {1,4,4,9} and the target is 8.


  • 0
    A

    The code takes care of that too. Identical numbers will be mapped to different values and the second part in the if condition sees that the number being considered right now does not count for the remaining number (target - nums[i]).


  • 0
    S

    Shouldn't the class used be unordered_multimap instead? unordered_map guarantees that each key is unique.

    In case the same key is used, this would also give you the wrong answer since the first index should be less than 2nd.


  • 0
    Z

    for test case (1 2 1) and target 2, your result would be [3, 1] instead of [1, 3].

    because for the find of first 1, it would return itself, and it would move on until the 2nd 1.


Log in to reply
 

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