015 3Sum[M]

02-25

1 題目描述

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

難度：Medium

2 題目樣例

For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]

3 題目分析

給出一個整數數組，要求返回其中所有的三數之和為0的組合。

（在經歷了諸如什麼"羅馬數字和整數相互轉化"等爛題後，遇到像3Sum這樣有一定思維深度的題目，我已經快感動的流出眼淚來了。= =）

之前我們遇到過與之最類似的題目是"Two Sum"，我們可以進行一番小小的類比。Two Sum問題是可以採用 $O(n^2)$ 的暴力演算法去解決的，但我們可以利用map對查找進行優化，使得每次查找的時間複雜度降低至 $O(lgn)$ ，從而起到了降低整體時間複雜度的作用。

對於這題我們可以故技重施。根據我的思路，兩層for語句的循環嵌套肯定是少不了的，但是在每次查找的時候，我們是不是能想一些辦法做做優化呢？（手動滑稽）

4 思路分析

其實是否利用map，大體上的思路都是一樣的：因為在本題中，主要的思路都是先算出兩個數的和，然後在數組中查找是否有數字和之前兩數之和互為相反數。如果有的話，就可以把結果存儲起來，最後一併返回。

正如我剛剛所說，兩次for語句的嵌套是少不了的，所以說時間複雜度至少是 $O(n^2)$ 。（如果各位有更好的方法能把時間複雜度降下來，請積極和我們聯繫。）

既然已經至少 $O(n^2)$ 了，那麼我們先對數組進行個排序（ $O(nlgn)$ ）肯定是不會增加總體的時間複雜度的了。

但在查找的時候，也是有一定的技巧的。我們可以從整個數組的開始和結束取出兩個數字，並取出第三個數與之求和。

若求和結果等於0，則將三個數加入結果之中，同時將兩側的下標向中間移動，直到不與之前取出的數字相同，避免出現重複的三元組。
sum > 0，因為數組有序，說明右側的數字過大，所以下標左移，故而執行back--。
sum < 0，因為數組有序，說明左側的數字過小，所以下標右移，所以執行front++。

代碼實現如下：

class Solution { public: vector<vector<int> > threeSum(vector<int> &num) { vector<vector<int> > res; std::sort(num.begin(), num.end()); for (int i = 0; i < num.size(); i++) { int target = -num[i]; int front = i + 1; int back = num.size() - 1; while (front < back) { int sum = num[front] + num[back]; if (sum < target) front++; else if (sum > target) back--; else { vector<int> triplet(3, 0); triplet[0] = num[i]; triplet[1] = num[front]; triplet[2] = num[back]; res.push_back(triplet); while (front < back && num[front] == triplet[1]) front++; while (front < back && num[back] == triplet[2]) back--; } } while (i + 1 < num.size() && num[i + 1] == num[i]) i++; } return res; } };

5 後記

使用map也只不過是利用了map的自動排序效果而已...還不如一次性排序來得痛快。

不過一提到map，我倒是突然想溫習一下紅黑樹的知識了QAQ。