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
