Ruby Accepted Solution O(n)


  • 0
    I
    # O(n) Solution
    # input numbers: array of unique integers
    # input target: sum of integers
    # output return indices of the two numbers such that they add up to a specific target. 
    # solution: lets assume a + b = target, therefore target - b = a, therefore store the key "target - b" and value index. And return it if found during "numbers" traversal.
    
    def two_sum(numbers, target)
      hash_map = Hash.new
      for i in 0..numbers.size - 1
        if hash_map.key?(numbers[i])
          return [hash_map[numbers[i]], i]
        else
          hash_map.store((target - numbers[i]), i)
        end    
      end
      return nil
    end
    
    # O(n square)
    # def two_sum(nums, target)
    #   for i in 0..nums.size - 1
    #     for j in 0..nums.size - 1
    #       if i == j
    #         next
    #       end
    #       # puts "Summing #{nums[i]} and #{nums[j]}"      
    #       if ((nums[i]+nums[j]) == target)
    #         return [i,j]
    #       end
    #     end
    #   end
    #   return []
    # end
    

Log in to reply
 

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