Day23 Leetcode Array系列----Two Sum

本次目標在這 30 天用 Ruby 或 JavaScript 完成Leetcode Array 相關的題目

本次題目 Two_Sum by Ruby

將數字陣列中相加等於 9 的數字組合取出

given_num = [2, 7, 11, 15, 1, 4, 5, 6, 3, 10]  

target    = 9

思考路線一

1. 取出一個數字與另外一個數字相加
2. 可以用迴圈的方式取一個數字
3. 再包一個迴圈取另一個數字
4. 要收集相加等於 9 的數字組合
5. 不可以出現重複的數字組合

Coding Time

先定義一個方法，並且把給予的數字陣列與目標傳入

given_num = [2, 7, 11, 15, 1, 4, 5, 6, 3, 10]  
target = 9

def two_sum(given_num,target)

end

p two_sum(given_num, target)

我打算用迴圈或遞迴的方式，因為可以把每個數字都取出來進行計算，再此考慮比較 Ruby 迴圈或遞迴的方法

• for
• each
• upto

用 for 迴圈可以把目標陣列中每一個元素都傳出並且用變數承接進行運算，也可以給一個範圍如 [0,1,2,3,4] 讓 for 迴圈使用。

用 each 迴圈也可以把目標陣列中每一個元素都傳出並且用變數承接進行運算，雖然可以用with_index把陣列元素的索引傳出，但靈活度沒有for 迴圈大

用 upto 可以要求做程式迴圈幾次，1.upto(5)就是從 1 做到 5，與for 迴圈相似

我選擇用for 迴圈解題，先准一個空陣列裝符合條件的數字組合，迴圈起始值，計算陣列的長度當作終止值，利用ruby的 * 在Array的功能可以把範圍炸開

def two_sum(given_num, target)
    
    result= []
    bottom = given_num.length-1 // -1 因為陣列索引是從0開始
    start = 0                  //  length則是陣列中元素數量
    
    for i in [*start..bottom] //[0,1,2,3,4,5,6,7,8,9]
    
    end
    
    return result
    
end

我能夠用第一個迴圈取得第一個數字，我想用第二個迴圈取得第二個數字，但是我不希望我第二次取到的數字與第一次相同，或者取出重複數字，所以我改變了第二次迴圈的起始值

def two_sum(given_num, target)
    
    result= []
    bottom = given_num.length-1
    start = 0
    
    for i in [*start..bottom]
        new = i+1 //改變起始值
    
        for j in [*new..bottom]
            
        end
    
    end
    
    return result

end

改變起始值，拿第一圈舉例

for i in [0,1,2,3,4,5,6,7,8,9]
             外
given_num = [2, 7, 11, 15, 1, 4, 5, 6, 3, 10]  
                內
for j in [1,2,3,4,5,6,7,8,9]

利用雙迴圈拿到 i 與 j 這兩個變數，可以用這兩個變數當作陣列的索引取得元素，取到元素後拿出來相加與目標值比較，符合條件就加入準備好的空陣列，整個數字陣列都判斷完畢後，回傳符合要求的數字組合

given_num = [2, 7, 11, 15, 1, 4, 5, 6, 3, 10]  
target = 9

def two_sum(given_num, target)
    
    result= []
    bottom = given_num.length-1
    start = 0
    
    for i in [*start..bottom]
        new = i+1
        
        for j in [*new..bottom]
            
            if  given_num[i] + given_num[j] == target
                result << [given_num[i],given_num[j]]
            end
        
        end
    
    end
    
    return result

end

p two_sum(given_num, target)

結果如下

[[2, 7], [4, 5], [6, 3]]

思考路線二

1. 藉由target找到對應值
2. 用迴圈選出一個數字去與target相減
3. 判斷數字陣列中有無對應值
4. 如果有就把這組數字存到結果
5. 把對應值從數字陣列中移除，避免出現鏡像結果

Coding Time

given_num = [2, 7, 11, 15, 1, 4, 5, 6, 3, 10]  
target = 9

def two_sum(given_num, target)
    result = []
    given_num.each do |num|
        another = target - num
        if given_num.include?(another)
            result << [num,another].sort
            # given_num.delete(another)
        end
    end
    p result
end

two_sum(given_num, target)

結果如下

[[2, 7], [4, 5], [3, 6]]

思考思路三 by 5xRuby KT

1. 準備一個空 hash (result)
2. 用迴圈取數字陣列的值(n)
3. 先把大於 9 的數字剔除
4. 用 9 扣掉 n (找對應值 another)
5. 做個判斷，如果 another 不是 result 的 key ，就把 n 存入 hash 並且給他一個 nil value
6. 如果 another 是 result 的 key，就把 n 成為 another 的 value
7. 最後用 reduce 加上 if 判斷把收集正確結果收集到 ary 裡面
8. 如果 result 裡面的鍵值對都有值，就把這一組鍵值對排序後放到 ary

Coding Time

given_num = [2, 7, 11, 15, 1, 4, 5, 6, 3, 10]  
target = 9
def two_sum(nums, target)
    result = {}
    nums.each_with_index do |n, idx|
      next if n > target
  
      another = target - n
      if result.keys.include?(another)
        result[another] = n
      else
        result[n] = nil
      end
    end
    result.reduce([]) do |ary, (k,v)| 
      ary << [k, v].sort_by(&:itself) if v
      ary
    end
end

result 收集到的內容

{2=>7, 1=>nil, 4=>5, 6=>3}

判斷是否有值後的結果

[[2, 7], [4, 5], [3, 6]]

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty