O(n) c++ using hashtable 44ms solution


  • 4
    H
    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            int n = numbers.size();
            unordered_map<int , int> mp;
            vector<int> nums;
            for(int i = 0 ; i < numbers.size() ; i++){
                if(mp.find(target-numbers[i]) != mp.end() 
                                      && i != mp[target-numbers[i]]){
                    nums.push_back(mp[target-numbers[i]]+1);
                    nums.push_back(i+1);
                }else{
                    mp[numbers[i]] = i;
                }
            }
            return nums;
        }
    };

  • 4
    S
     class Solution {
        public:
            vector<int> twoSum(vector<int> &numbers, int target) {
                vector<int> result;
                vector<int> num = numbers;
                int count = numbers.size();
                if(numbers.empty()){
                    return result;
                }//if
                sort(numbers.begin(),numbers.end());
                for(int i = 0,j = count-1;i < j;){
                    int sum = numbers[i] + numbers[j];
                    if(sum == target){
                        return FindIndex(num,numbers[i],numbers[j]);
                    }
                    else if(sum > target){
                        j--;
                    }
                    else{
                        i++;
                    }
                }//for
                return result;
            }
        private:
            // Find index of num
            vector<int> FindIndex(vector<int> &numbers,int num1,int num2){
                int count = numbers.size();
                vector<int> result;
                int index1,index2;
                bool flag1 = false,flag2 = false;
                for(int i = 0;i < count;++i){
                    if(flag1 == false && numbers[i] == num1){
                        index1 = i+1;
                        flag1 = true;
                    }
                    else if(flag2 == false && numbers[i] == num2){
                        index2 = i+1;
                        flag2 = true;
                    }
                }//for
                // index1 < index2
                if(index1 > index2){
                    int tmp = index1;
                    index1 = index2;
                    index2 = tmp;
                }//if
                result.push_back(index1);
                result.push_back(index2);
                return result;
            }
        };
    

    enter image description here


  • 0
    M

    map is binary search tree, unordered_map is hashtable


  • 0
    R

    This is actually O(nlog(n)) time complexity


  • 0
    R

    switch map 2 unordered_map will increase the performance a lot.
    and the if statement in the loop, can just keep the first part. just my opinion


  • 0
    R

    another brilliant idea~~


  • 0
    H

    using unordered_map , time decreased to 25ms... Thanks for your suggestion guys..


  • 0
    R

    sort(numbers.begin(),numbers.end());
    it makes the program O(nlogn)


Log in to reply
 

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