## 一、題目描述  ## 二、解題技巧 這道題從表面上看與3Sum極其相似，事實上確實可以使用相同的思維和方法，只不過這樣做的話，時間復雜度為O(n^3)，空間復雜度為O(1)將超時。 這道題也可以在排序之后先計算后面兩個數的和，將其方法一個哈希表中，由于可能存在不同的兩個數的和為相同值，因此，可以考慮將和為相同的值放在一個鏈表中，然后將變量頭放在哈希表中。然后再按照3Sum的思路，不過第三個數在這里變成了第三個和第四個數的和，通過哈希表可以方便地找到和為固定值的數的鏈表，就可以找到符合條件的四個數。這種方法的時間復雜度為O(n^2),空間復雜度也為O(n^2)。 ## 三、實例代碼 ~~~ // 該算法使用3Sum的思路來實現 #include <iostream> #include <algorithm> #include <vector> using namespace std; class solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > result; int Size = num.size(); if (Size < 4) return result; // 對輸入的數據進行排序 sort(num.begin(), num.end()); for (int first = 0; first < (Size - 3); first++) { if ((first != 0) && (num[first] == num[first - 1])) { continue; } int first_num = num[first]; for (int second = first + 1; second < (Size - 2); second++) { if ((second != first + 1) && (num[second] == num[second - 1])) { continue; } int second_num = num[second]; int third = second + 1; int forth = Size - 1; // 對第三和第四個數進行左右夾逼 while (third < forth) { int third_num = num[third]; int forth_num = num[forth]; int Sum = first_num + second_num + third_num + forth_num; if (Sum == target) { // 存放一維數據 vector<int> temp; temp.push_back(first_num); temp.push_back(second_num); temp.push_back(third_num); temp.push_back(forth_num); // 將組合存入容器result中 result.push_back(temp); third++; while ((third < Size - 1) && (num[third] == num[third - 1])) { third++; } forth--; while ((forth > second) && (num[forth] == num[forth + 1])) { forth--; } } if (Sum > target) { forth--; while ((forth > second) && (num[forth] == num[forth + 1])) { forth--; } } if (Sum < target) { third++; while ((third < Size) && (num[third] == num[third - 1])) { third++; } } } } } return result; } }; ~~~ 測試： ~~~ #include "solution.h" using namespace std; int main() { solution a; int size = 200; // 數據的個數 vector<int> num(size); // 用于存放數據的容器 vector<vector<int> > result; // 存放算法的運行結果 for (int i = 0; i < size; i++) num.push_back(rand() % 30 - 20); // 隨機生成數據 int target = 0; result = a.fourSum(num, target); for (vector<vector<int> >::size_type j = 0; j < result.size(); j++) { for (vector<int>::size_type k = 0; k < result[j].size(); k++) { cout << result[j][k] << " "; } cout << endl; } getchar(); return 0; } ~~~ 一個輸出結果：  ## 四、體會 這道題是3Sum的一種延伸，但需要轉化一種思路以降低計算復雜度。如果僅僅按照3Sum的延伸來做這道題的話，算法的空間復雜度會達到O(n^3)，但是空間復雜度為O(1)。可以換一種思路，在排序之后，先計算后面兩個數的和，并用哈希表存儲起來，然后就將問題轉變為了3Ssum的問題，只不過計算出第三個數之后，還需要在哈希表中找到和滿足條件的第三個數和第四個數。