## 一.題目描述  ## 二.解題技巧 這道題和另外一道題Two Sum很類似，不過這道題是在數組中尋找三個數，使得其和為0，同時要求這三個數只能出現一次。如果單純得使用暴力算法來做的話，時間復雜度為O(n^3)，且很難判斷這一組數是否已經出現過。 若是選擇先排序，然后左右夾逼，復雜度：O(n2)。? 這個方法可以推廣到k-sum，先排序，然后做k-2 次循環，在最內層循環左右夾逼，時間復雜度是：O(max(n*logn, n^(k-1)))。 如果考慮將數組A(元素個數為n)進行升序排序，那么按照順序將數組中的第i個數作為三個數中最小的數，尋找從A的第i+1個數到n-1個數中滿足和為-A[i]的數，就可以找到滿足三個數和為0的組合了，但是，單獨考慮這種情況，會出現重復的問題。要保證不出現重復的情況，當i!=0時，如果第i個數與第i-1個數相同的話，則不進行處理，直接處理第i+1個元素。這樣，只要保證三個數中最小的數是按照順序遞增的，那么算法找到的解就都是不重復的。 這道題的邊界條件在于：由于我們選擇的是三個數中的最小值，因此，對于這個數的循環是[0, n-2)，同時，要對最小值進行消除重復的元素時，需要從第1個元素開始判斷，如果從第0個元素開始判斷的時候，可能會將0，0，0這種情況忽略掉，因此，在消除重復的最小元素時，必須從第1個元素才開始。 這道題在尋找數組A中的兩個數的和為-A[i]時，可以考慮利用數組A是已經排序的條件，進行左右夾逼操作。在進行左右搜索的時候，需要將左右兩邊收縮到與當前元素不同的元素為止，這樣做有兩個原因：1.可以減少計算量；2.當當前的兩個元素的和剛好等于-A[i]的時候，如果沒有進行上面的縮放操作，那么就可能將重復的三個數保存下來，導致結果出錯。 ## 三.實現代碼 ~~~ #include <iostream> #include <vector> #include <algorithm> using namespace std; class solution { public: vector<vector<int>> threeSum(vector<int> &num) { int size = num.size(); vector<vector<int>> result; if (size < 3) return result; sort(num.begin(), num.end()); // 參數為起點和終點 for (int index = 0; index < (size - 2); index++) { int first = num[index]; int second = num[index + 1]; const int target = 0; // 以下操作排除重復組合的情況 if ((index != 0) && (first == num[index - 1])) continue; int start = index + 1; int end = size - 1; while (start < end) { second = num[start]; int third = num[end]; int Sum = first + second + third; if (Sum == target) { vector<int> temp; temp.push_back(first); temp.push_back(second); temp.push_back(third); result.push_back(temp); start++; end--; while (num[start] == num[start - 1]) start++; while (num[end] == num[end + 1]) end--; } if (Sum > target) { end--; while (num[end] == num[end - 1]) // 避免出現重復的整數 end--; } if (Sum < target) { start++; while (num[start] == num[start + 1]) //避免出現重復的整數 start++; } } } return result; } }; ~~~ 測試代碼： ~~~ // 測試代碼 #include "solution.h" using namespace std; int main() { int num = 100; vector<int> number(100); for (int i = 1; i < num; i++) number.push_back(rand() % 100 - 30); // 隨機生成一組數據 vector<vector<int>> result; solution Sum; result = Sum.threeSum(number); // 執行算法并返回結果至result // 訪問元素,result是多維的，需使用多個for循環 cout << "三個數的和為零的組合有：" << endl; for (vector<vector<int>>::size_type i = 0; i < result.size(); i++) { for (vector<int>::size_type j = 0; j < result[i].size(); j++) { cout << result[i][j] << " "; } cout << endl; } getchar(); return 0; } ~~~ 以下是網上的一種解決方法： ~~~ // LeetCode, 3Sum // 先排序，然后左右夾逼，注意跳過重復的數，時間復雜度O(n^2)，空間復雜度O(1) class Solution { public: vector<vector<int>> threeSum(vector<int>& num) { vector<vector<int>> result; if (num.size() < 3) return result; sort(num.begin(), num.end()); const int target = 0; auto last = num.end(); for (auto i = num.begin(); i < last - 2; ++i) { auto j = i + 1; if (i > num.begin() && *i == *(i - 1)) continue; auto k = last - 1; while (j < k) { if (*i + *j + *k < target) { ++j; while (*j == *(j - 1) && j < k) ++j; } else if (*i + *j + *k > target) { --k; while (*k == *(k + 1) && j < k) --k; } else { result.push_back({ *i, *j, *k }); ++j; --k; while (*j == *(j - 1) && *k == *(k + 1) && j < k) ++j; } } } return result; } }; ~~~ ## 四.總結 我自己的想法時，將數組進行排序，然后按照順序選擇數組A[1, n-1)中的元素作為三個數中的中位數來在剩下的已經排好序的數組中尋找滿足條件的其他兩個數。但是，選擇中位數的這種情況需要考慮的邊界條件比較復雜，并沒有選擇最小值來得方便一些，同時，選擇中位數之后，將已經排序的數組分成了兩段，這樣在進行收縮的時候，需要分別判斷兩個兩邊與i的關系，也比較容易出錯。 這道題通過對數組進行排序，從而按照順序選擇不同的最小值來避免出現重復的情況，這確實是一個比較好的編程技巧。