C++ two solutions, sort O(nlogn) and hashmap O(n)


  • 2

    sort the array, find the two values, then find the index. Time complexity O(nlogn), space complexity O(n).

    Because the sort() will change the indexes of the num, we need a backup of data, which costs extra space.

    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> nums_temp = nums;
        sort(nums_temp.begin(),nums_temp.end());
        vector<int> res;
        int i=0,j=nums_temp.size()-1;
        while(i<j){
            if (nums_temp[i]+nums_temp[j]==target){
                for (int k=0;k<nums.size();k++){
                   if (nums[k]==nums_temp[i] || nums[k]==nums_temp[j]){
                       res.push_back(k);
                   }
                }
                break;
            }else if (nums_temp[i]+nums_temp[j]>target){
                j--;
            }else{
                i++;
            }
        }
        return res;
    }
    

    or we can use hash map, time complexity O(n), space complexity O(n)

     vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        unordered_map<int,int> map;
        for (int i=0;i<nums.size();i++){
            if (map.count(target-nums[i])){
                res.push_back(map[target-nums[i]]);
                res.push_back(i);
                break;
            }else{
                map[nums[i]]=i;
            }
        }
        return res;
    }

Log in to reply
 

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