LeetCode Link

Problem Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Idea

思路就是用个Hash，缓存每个数字的index
注意这里如果无脑直接缓存的话有个小陷阱，测试用例会给类似[3,3] 6这种，于是如果一开始就更新index，那么会覆盖掉一个相同的element的index

Solution

Solution 1

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    # because each input would have exactly one solution, so we do
    # no check the only-one-element situation
    table = Hash.new
    table[nums[0]] = 0
    nums.each_with_index do |num, index|
        unless table[target - num].nil? then
            unless index == table[target-num]
                low_index = [index, table[target-num]].min
                high_index = [index, table[target-num]].max
                return [low_index, high_index]
            end
        end
        table[num] = index # problem, same value will have hash confilct
    end
end

Solution 2: more ruby

def two_sum(numbers, target)
    hash = numbers.map.with_index.to_h
    found = numbers.find.with_index do |n, index| 
      target_index = hash[target - n] and target_index != index
    end
    [numbers.index(found), hash[target - found]].sort
end

个人感觉这个solution的缺点在于，需要把nums全部map

Review