LeetCode： Two Sum

Question

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 1:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1]

---

Solution

先新增ㄧ個空白的 Hash 命名為 dict。 接著以 each_with_index 方法可以把 nums(Array 型態) 裡面的元素及位置逐個取出。 然後再利用 Hash 來記錄 nums 裡的每個元素及位置。

這裡放 if 是要以 『target 減去 nums 裡的元素』為 key 找出在 dict 記錄簿裡是否有對應的值。 如果沒有比對成功，代表 dict 記錄簿中沒有該元素的 key-value pair，就會在第 7 行寫入 dict。 當比對成功時，代表有找到兩個相加會等於 target 的值，最後在第 5 行回傳位置即可通過測驗。

以上面範例來說：nums = [2, 7, 11, 15], target = 9

在 each_with_index 方法中跑第一圈時，會看 Hash dict[9-2] 有沒有存在？ 由於ㄧ開始的 Hash dict 是空白的， 所以 dict[7] 會是 nil。 接著直接跳到第 7 行並紀錄 dict[2] = 0, { 2=>0 }。

第二圈的時候，會ㄧ樣檢查 dict[9-7] 有沒有存在？ 因為在第一圈有記錄到 dict[2] = 0，所以會進入 if 邏輯裡面，並且回傳 dict[2] 的 value 值為 0，以及 index 值為 1。

1   def two_sum(nums, target)
2     dict = {}
3     nums.each_with_index do |n, i|
4       if dict[target - n]
5         return dict[target - n], i
6       end
7       dict[n] = i
8     end
9   end