Two Sum

Posted on | In

題目

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

思路

兩數相加= target，若兩數相同，則兩數都為target的一半；若兩數不同，則一個會大於target的一半，另一個會小於target的一半。所以第一個想法是先以(target/2)作為分界，將nums分成大於他及小於他的兩個array，然後從其中一個array的每個項目開始，看看是否能在另一個array中找到一個數字能相加後等於target。

Pseudocode

1
2
3
4
5
6
7
8
a = target/2

如果nums中有兩個a，那麼直接回傳這兩個數字在nums中的index

如果沒有
  x = 小於等於a的陣列
  y = 大於a的陣列
  從x的每項去運算，看看是否能在y中找到target-x，找到就回傳x及y子項目在nums中的index

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def two_sum(nums, target)

  a = target / 2.0

  if nums.count(a) == 2
    index1 = nums.index(a)
    nums[index1] = nil
    index2 = nums.index(a)
    return [index1, index2]
  end

  x = nums.select{|i| i <= a}
  y = nums.select{|i| i > a}

  (0...x.length).each do |i|
    if y.include?(target - x[i])
      return [nums.index(x[i]), nums.index(target - x[i])].sort
    end
  end  
end                             # Runtime : 219 ms

分析

此演算法的運作時間：

  • nums.count(a)為O(n)
  • 兩次nums.select皆為O(n)
  • each迴圈裡包著include?，是為O(n2)

整體Time complexity 為 O(n2)

參考他人作法

1
2
3
4
5
6
7
8
def two_sum(nums, target)
  search = {}

  nums.each_with_index do |num, i|
    return [search[targt-num], i] unless search[target-num].nil?
    search[num] = i
  end
end                            # Runtime : 59 ms

分析

利用Hash來儲存已經找尋過的num及他的index，如此一來就不需要寫兩個迴圈，只需往後找target-num是否存在Hash裡，就能知道答案了。由於each迴圈為O(n)，而Hashtable為O(1)，所以整體的Time complexity只有O(n)。