My C++ code (unordered_map used) O(n) space, O(n) time


  • 6
    D
    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            vector<int> res;
            int i, vSize;
            unordered_map<int, int> numMap;
            vSize = numbers.size();
            unordered_map<int,int>::const_iterator fIdx;
            
            if(vSize>1)
            {
                for(i=0;i<vSize; i++)
                {
                    fIdx = numMap.find(target - numbers[i]);
                    if(fIdx != numMap.end())
                    { // if its pal is already in the map, then return 
                        res.push_back(fIdx->second);
                        res.push_back(i+1);
                        break;
                    }
                    else
                    { // insert itself to the map
                        numMap[numbers[i]] = i+1;
                    }
                }
            }
            return res;
        }
    };

  • 0
    U
    This post is deleted!

  • 0
    B

    Is find() function really O(1) ?


  • 0
    B

    sorry," We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index."


Log in to reply
 

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