Two Sums (Brute-force and optimized solution)

TowSumsRuby.md

Two Sums

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Example 2:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution

1 (BAD approach, Good first step) super easy time consuming N²

• two for loops, get result out put index from each loop

def two_sum(nums, target)
  result = [] 
  nums.each_with_index do |num1, i|
        nums.each_with_index do |num2, j| 
        next if i == j  # dont want the index to be same
        if num1 + num2 == target
                result= [i, j].sort
            end
        end   
    end
    result    
end

2 (Better optimized) using key-value pair aka = dict, hash map, obj

• single loop storing previos value as key for next element reference

def two_sum(nums, target)
  result = {}
  nums.each_with_index do |num, i|
      if result[target-num] # check if we have an index aassinged to key target - number 
          return result[target-num], i 
      end # other wise add a key (num) with value (index) to Hash  
      result[num]=i
    end
    result    
end