Leetcode Exercise 1

Two Sum

Two Sum - LeetCode

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.

給你一組整數的陣列(Array)，需要回傳兩個數字的索引(index)，兩個數字相加等於指定的目標(target)。

每個題目只有一個解，不能使用相同的元素兩次。

Example

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

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

構思

1. target-nums[0]=x
2. 從nums中找出x
3. 有找到的話就return 0 和 n 的索引
4. 沒有的話回到第一步，變成nums[0+1]

實作程式碼

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
  for n in 0...nums.length
    x = target-nums[n]
    ans = nums.find_index(x)
    if ans && n!=ans
      return n, ans
    end
  end     
end

find_index(obj) → int or nil 找到第一個和obj相同的元素後回傳其索引

結果

beats 33.54%😭

Runtime最短的寫法: 36 ms

def two_sum(nums, target)
  indices = {}
  nums.each_with_index do |num, idx|
    if indices.has_key?(target - num)
      return [indices[target - num], idx] 
    end
    indices[num] = idx
  end
end

each_with_index 可以同時操作 value 和 index，第一個為 value，第二個為 index，從0開始。

has_key?(key) 當給的key存在於hash中時，回傳true

可以從下圖大致了解程式運作過程