My 15ms Accepted C++ O(n*log(n)) Solution


  • 5
    L
    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            vector<int> v = numbers;
            sort(v.begin(), v.end());
            int left = 0;
            int right = (int) v.size() - 1;
            int middle;
            while (left < right) {
                int middle = v[left] + v[right];
                if (middle == target) break;
                if (middle < target) 
                    ++left; 
                else 
                    --right;
            }
    
            int result_index1;
            int result_index2;
            for (int i=0;i<v.size();++i) {
                if (numbers[i] == v[left]) { 
                    result_index1 = i; 
                    break;
                }
            }
    
            for (int i=(int)v.size()-1;i >= 0;--i) {
                if (numbers[i] == v[right]) {
                    result_index2 = i; 
                    break; 
                }
            }
    
            if (result_index1 > result_index2) 
                swap(result_index1,result_index2);
    
            vector<int> result {result_index1 + 1, result_index2 + 1};
            return result;
        }
    };
    

    enter image description here


  • 0
    J

    I sort by Quick_Sort() with vector,then time out.....


  • 0
    D

    thanks for sharing!!


  • 1
    M

    Thanks for sharing. Your answer is kind of two pointers solution. Without checking two times and hashmap, there is another simple version.

    vector<int> twoSum(vector<int>& nums, int target) { //two pointers
        vector<pair<int, int>> temp;
        for(int i=0; i<nums.size(); i++) {
            temp.push_back(make_pair(nums[i], i)); //first:number, second:index
        }
        sort(temp.begin(), temp.end());
        vector<int> ans;
        int left=0, right = nums.size()-1;
        while(left < right) {
            if(target == temp[left].first + temp[right].first) {
                ans.push_back(temp[left].second+1);
                ans.push_back(temp[right].second+1);
                sort(ans.begin(), ans.end());
                return ans;
            }
            else if(target > temp[left].first + temp[right].first)  left++;
            else right--;
        }
        //return ans;
    }

  • 0
    F

    vector<int> v = numbers;
    sort(v.begin(), v.end());

    container copy and sort ,then find the index in old vector. it is terrible


Log in to reply
 

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