15-line c++ without hash


  • 13
    M
    class Solution {
    public:
    
        vector<int> twoSum(vector<int>& nums, int target) {
            vector<int> ns=nums;
            sort(ns.begin(), ns.end());
            int a=0, b=ns.size()-1;
            
            while (a < b)
                if (ns[a]+ns[b] > target) b--;
                else if (ns[a]+ns[b] < target) a++;
                else break;
    
            vector<int> ans;
            for (int i=0; i<nums.size(); i++) {
                if (nums[i]==ns[a]) ans.push_back(i+1);
                else if (nums[i]==ns[b]) ans.push_back(i+1);
            }
            if (ans[0]>ans[1])
                swap(ans[0], ans[1]);
            return ans;
        }
    };

  • 0
    I

    Just curious. Why is this a good solution? The space complexity is still O(n), yet the time is O(nlogn). Why would someone use this rather than using a hash which also use O(n) space but only O(n) time?


Log in to reply
 

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