18. 4Sum

 18. 4Sum

難度: Medium

類型: Array, Two Pointers, Sorting

CPP程式下載: 18_1.cpp 18_2.cpp

前情題要:

四個數字加總起來等於 target

思考方式:

1. Vector 先排序

2. 用 2Sum 的 left (n2), right (n3), 再加上頭尾 (n1, n4)。

3. 找到對的組合時, 填進 Set。(Set 會判斷是否唯一)

4. 把 Set 用 Vector.assign(set.begin(), set.end()) 的方式轉成 Vector 再 return。

5. 18_1.cpp 的 n1與n4迴圈, 並沒有優化, 花的時間是 200ms 上下。如果如18_2.cpp 連續抓四個值的和來判斷迴圈是否需要繼續或結束, 花的時間降到41ms多一些。雖然沒在前段班(15.34%花7ms, 64.37%花23ms), 但也相差不遠。就先優化到這就夠了。

複雜度思考:

Time Complexity: O( (N-3)*(N-3)*(N-3) ) 

Space Complexity: O( 1 )

結果:

Runtime: 41 ms, Beats: 17.95%

Memory: 25.13 MB, Beats: 15.61%