Leet Code: 4Sum II

Swift

暴力解

直接遍歷所有加總組合，複雜度會變成 O(n⁴) 成長，其中4次方為全部輸入 Array組數，n為每個陣列裡的元素個數 ; 若給予5個陣列，便會成長為 O(n⁵)，相當危險。

Time Limit Exceeded

對半拆組，第一組建立總和字典，第二組遍歷時計算次數

將數列組合均分拆成兩組，第一組加總時便建立字典，key 為總和，value 為總和重複的次數。輪到第二組加總時，一邊遍歷一邊查找是否有相符的字典 key（正負調換），若有相符則其 value 即為加總為零的組合數。

此方法的好處是可以確保執行時間複雜度壓縮在 O(n²) (準確為O(2n²)，常數可忽略)，其中2次方為陣列組數的一半，若今天給予六組陣列，則為 O(n³)。

Runtime: 284 ms (Beat 81.40%)

Memory Usage: 26.4 MB (Beat 74.42%)