Ruby solution


  • 0
    J

    I tried this in a few ways. There's the standard O(n^2) solution, which takes a blazing 5.5 seconds to complete:

     def two_sum(nums, target)
        (0...nums.length).each do |i|
            start = i + 1
            (start...nums.length).each do |j|
                if nums[i] + nums[j] == target then return [i, j] end
            end
        end
    end
    

    Then, I tried using sorting (nlogn, with some additional n iterations), which was kind of a pain because I had to store the original array indices. This dropped the runtime by nearly two powers of ten (to 85ms):

    def two_sum(nums, target)
        i = 0
        j = nums.length - 1
        
        nums = nums.each_with_index.map{ |x,i| [x, i]}.sort
        while true do
            total = nums[i].first + nums[j].first
            if total == target
                return [nums[i].last, nums[j].last]
            elsif total > target
                j -= 1
            else
                i += 1
            end
        end
    end
    

    Lastly, I tried using a hash lookup (dropping the algorithm down to O(n)), which gave me a small but noticeable improvement to 69ms:

    def two_sum(nums, target)
        indices = {}
        nums.each_with_index do |x,i|
            indices[x] = i
        end
        
        answer = []
        nums.each_with_index do |x,i|
            j = indices[target - x]
            if  j && j != i
                answer = [i, j]
                break
            end
        end
        return answer
    end
    

    Any thoughts, or suggestions on how to improve?


Log in to reply
 

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