8ms C++ solution beats 98.34%


  • -2
    K
    #include <vector>
    #include <algorithm>
    //8ms
    class Solution {
    public:
        struct str{
            int id;
            int val;
            str(){}
            str(int id, int val){this->id = id; this->val = val;}
            bool operator<(const str a){
                return val<a.val;
            }
        };
        int idx(str *&nums, int l, int r, int val){
            if(l>r)
                return -1;
            int m = (r-l)/2+l; //avoid int overflow
            if(nums[m].val == val){
                return m;
            }else if(nums[m].val < val){
                return idx(nums, m+1, r, val);
            }else{
                return idx(nums, l, m-1, val);
            }
        }
        vector<int> twoSum(vector<int>& nums, int target) {
            int n = nums.size();
            int tmp=0;
            str* mystr= new str[n];
            for (int i = 0;i<n;i++){
                mystr[i] = str(i,nums[i]);
            }
            sort(mystr, mystr + n);
            for(int i = 0;i<n;i++){
                if((tmp = idx(mystr, i+1, n-1, target-mystr[i].val))!=-1){
                    vector<int>ans(2,0);
                    ans[0] = mystr[i].id;
                    ans[1] = mystr[tmp].id;
                    return ans;
                }
            }
        }
    };

Log in to reply
 

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