O(nlogn) solution in C++.


  • 0
    8
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct Node
    {
    int idx,num;
    Node(int i,int n)
    :idx(i),num(n){}
    bool operator <(const Node& b)const 
    {
        return num<b.num;
    }
    };
    class Solution {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>vec;
        vector<Node>nodes;
        
        for(int i=0;i<nums.size();i++) nodes.push_back(Node(i,nums[i]));
        sort(nodes.begin(),nodes.end());
        sort(nums.begin(),nums.end());
        
        int size=nums.size();
        for(int i=0;i<size;i++)
        {
            int pos=lower_bound(nums.begin(),nums.end(),target-nums[i])-nums.begin();
            if(pos!=i&&nums[pos]+nums[i]==target)
            {
                int maxed=max(nodes[pos].idx,nodes[i].idx);
                int minn=min(nodes[pos].idx,nodes[i].idx);
                vec.push_back(minn+1);
                vec.push_back(maxed+1);
                break;
            }
            else if(pos==i&&nums[pos]*2==target)
            {
                if(pos>0&&nums[pos-1]==nums[i]) 
                {
                    vec.push_back(nodes[pos-1].idx+1);
                    vec.push_back(nodes[pos].idx+1);
                    break;
                }
            }
        }
        return vec;
    }
    

    };


Log in to reply
 

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