Day7 Leetcode Array系列---- 3Sum

本次題目 3Sum by Ruby

現在有 1 個數字陣列，目標是找出陣列裡 3 個數字加總為 0 ，這 3 個數字的索引不可以一樣，最後將所有結果輸出成 Array

given_array_nums = [-1, 0, 1, 2, -1, -4]
output = [[-1, 0, 1],[-1, -1, 2]]

思考路線

1. 準備 result = [] 裝加總為 0 的數字組合
2. 以迴圈的方式去找，有三個數字所以用三個迴圈
3. 判斷迴圈取出的數字加總是不是 0
4. 如果加總為0 把這組數字排序後加進 result
5. 最後回傳的 result 要去除重複的組合
6. 仔細想想，我們不需要讓迴圈跑這麼多次，現在要剔除不用跑的次數

Coding Time

準備好 result 加上簡單的測試

given_array_nums = [-1, 0, 1, 2, -1, -4]
output = [[-1, 0, 1],[-1, -1, 2]]

def sum_zero( arr )
    result = []
    
end

def expect(a,b)
    p a
    p a == b
end

準備三個迴圈，迴圈長度就用輸入陣列長度

def sum_zero( arr )
    result = []
    for i in [*0..arr.size]   
        for j in [*0..arr.size]
            for k in [*0..arr.size]
                
            end
        end
    end
    return result
end

把加總為 0 的數字組合收集、排序後塞到 result 中、回傳的 result 要把重複組合去除

ef sum_zero( arr )
    result = []
    for i in [*0..arr.size]   
        for j in [*0..arr.size]
            for k in [*0..arr.size]
                if arr[i] + arr[j] + arr[k] == 0
                    
                    result << [arr[i],arr[j],arr[k]].sort
                end
            end
        end
    end
    return result.uniq
end

現在要去除不需要跑的次數，希望內部迴圈選出的數字不會與外部迴圈相同，所以要改變迴圈的起始值，而且外部迴圈並不需要跑到最後一個數字，依照這個想法，最外部的迴圈只要跑 [0,1,2,3] 這些索引，中間迴圈 [1,2,3,4] 這些索引，內側迴圈 [2,3,4,5] 這些索引

ef sum_zero( arr )
    result = []
    for i in [*0..arr.size-1-2]   
        for j in [*i+1..arr.size-1-1]
            for k in [*j+1..arr.size-1]
                if arr[i] + arr[j] + arr[k] == 0
                    
                    result << [arr[i],arr[j],arr[k]].sort
                end
            end
        end
    end
    return result.uniq
end

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

Daily kitty