iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

從真「新」鎮出發!30天的刷題修行篇,讓寫程式成為新必殺技系列 第 9

Two Sum 演算法初階題,Ruby 30 天刷題修行篇第九話

大家好,我是阿飛,今天的題目是演算法初階題目 Two Sum,讓我們一起來看看:
題目來源 Codewars


Write a function that takes an array of numbers (integers for the tests) and a target number. It should find two different items in the array that, when added together, give the target value. The indices of these items should then be returned in a tuple like so: (index1, index2).

For the purposes of this kata, some tests may have multiple answers; any valid solutions will be accepted.

The input will always be valid (numbers will be an array of length 2 or greater, and all of the items will be numbers; target will always be the sum of two different items from that array).

twoSum [1, 2, 3] 4 === (0, 2)

題目要我們把陣列中的數字兩兩相加,直到相加的結果等於 target,並且回傳兩個數字在陣列的 index。

看到題目我很快就聯想到,以前學 JavaScript 時練習過的印出九九乘法表,便假定要用兩個迴圈來完成,假設有陣列[0, 1, 2],而目標值是 3,我們第一圈計算 0 + 1 (index 0 和 1)和 0 + 2(index 0 和 2),得到結果分別是 1 和 2,不符合目標值,便進入第二圈,計算 1 + 2(index 1 和 2),便可以得到解答。故,內層的迴圈比起外層的迴圈,起始值要 + 1。

以下是我的解答:

def two_sum(numbers, target)
  i = 0
  j = 1
  arr = []
  
  while i < numbers.length
    while j < numbers.length
      if numbers[i] + numbers[j] == target
          arr << i
          arr << j
        break
      end
      j += 1
    end
    i += 1
    j = i + 1
  end
  arr
end

對比最佳解答:

def twoSum(numbers, target)
  numbers.each_with_index do |n1, i1|
    numbers.each_with_index do |n2, i2|
      return [i1, i2] if (n1 + n2) == target && i1 != i2
    end
  end
end

它很高明地用了 each_with_index 拿出陣列裡的每個 element 和對應的 index,並在最後加了 i1 != i2 的判斷,避免相同 index 數字相加的情況。

好了,今天解題就到這,大家晚安~


上一篇
資料型別轉轉轉,Ruby 30 天刷題修行篇第八話
下一篇
誰比誰長,迴圈和 reduce 用法,Ruby 30 天刷題修行篇第十話
系列文
從真「新」鎮出發!30天的刷題修行篇,讓寫程式成為新必殺技16

尚未有邦友留言

立即登入留言