DEV Community

hwangs12
hwangs12

Posted on

Two Sum - O(n) Solution


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



        unordered_map<int, int> hash;
        vector<int> result;

        for (int i = 0; i < nums.size(); ++i)
        {
            int numToFind = target - nums[i];

            if (hash.find(numToFind) != hash.end())
            {
                result.push_back(hash[numToFind]);
                result.push_back(i);
                return result;
            }
            else
            {
                hash[nums[i]] = i;
            }
        }



        return result;

    }
};


Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
vidhanshu profile image
vidhanshu borade

in worst_case unordered_map insertion takes O(n^2) time
and also you are using find function in worst _case it will take O(n) time it is O(n^2) solution then.
referece: geeksforgeeks.org/how-to-use-unord....