What is the error in this c++ code??


  • 0
    B
    vector<int> twoSum(vector<int>& nums, int target) {
        int l,r;
        vector<int> res;
        sort(nums.begin(),nums.end());
        l=0;
        r=nums.size()-1;
        while(l<r)
        {
            if(nums[l]+nums[r]==target)
            {
                    res.push_back(l+1);
                    res.push_back(r+1);
                    return res;
    
            }
            else if(nums[l]+nums[r]<target)
            {
                l++;
            }
            else
                r--;
        }
    }
    

    };


  • 0
    L

    Is there a TLE? remove sorting and use hash to improve it


  • 0
    B

    No TLE but there are some output errors .Why??


  • 0
    C

    In your codes logic, you changed the original order by sort operation.


  • 0
    T

    The function "sort" changed indices of input vector.
    You may use std::pair to record original order of vector, just like this:

    static bool Greater(pair<int,int> elem1, pair<int,int> elem2)
    {
        return elem1.first < elem2.first;
    }
    
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> nums2;
        for(int i = 0; i < nums.size(); i++)
        {
            pair<int,int> p = make_pair(nums[i], i + 1);
            nums2.push_back(p);
        }
        sort(nums2.begin(), nums2.end(), Greater);
        int j = 0;
        int k = nums2.size() - 1;
        vector<int> result;
        while(1)
        {
            if(nums2[j].first + nums2[k].first == target)
            {
                result.push_back(min(nums2[j].second, nums2[k].second));
                result.push_back(max(nums2[j].second, nums2[k].second));
                return result;
            }
            else if(nums2[j].first + nums2[k].first > target)
            {
                k--;   
            }
            else
            {
                j++;
            }
        }
    }
    

    By the way, because of sorting process, this is an O(nlogn) algorithm. You may use Hashmap to get an O(n) solution. : )


Log in to reply
 

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