O(nlogn) solution. runtime beats 85.58%


  • 4
    N
    #include<stdio.h>
    #include<vector>
    #include<algorithm>
    using namespace std;
    struct an
    {
        int val,ind;
    };
    bool comp(an a, an b)
    {
        return a.val<b.val;
    }
    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int>b;
            int l=0,r=nums.size()-1;
            vector<an>h;
            for(int i=0;i<nums.size();i++)
            {
                an temp;
                temp.val=nums[i];
                temp.ind=i;
                h.push_back(temp);
            }
            sort(h.begin(),h.end(),comp);
            while(l<r)
            {
                if(h[l].val+h[r].val==target)break;
                if(h[l].val+h[r].val>target)r--;
                else l++;
            }
            b.push_back(h[l].ind);
            b.push_back(h[r].ind);
            return b;
        }
    };

Log in to reply
 

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