一、題目鏈接

四數之和

二、題目

三、題目解析

題目要求基本與三數之和一樣。

四、算法原理

解法幾乎照搬三數之和

解法一：排序 + 暴力枚舉 + 利用 set 去重

絕對超時，時間復雜度是O(n^4)。

解法二：排序 + 雙指針

示例1排好序：

步驟：

1. 排序
2. 從左向右依次固定一個數a
3. 在a的右區間內，利用"三數之和"找到三個數，使這三個數之和等于target - a即可：從左向右依次固定一個數b，在b的右區間內利用"雙指針"找到兩個數，使這兩個數之和等于target - a - b即可。

代碼大體樣子：兩層for循環，中間套了一個雙指針算法。不過這只是大體樣子，還需要解決和"三數之和"同樣的細節問題：結果不重且不漏。

不重："三數之和"僅有兩個地方。因為這里多了一個數，所以有3個地方要保證不重

• 找到一個四元組結果，left和right都要跳過重復元素
• 每使用完一遍"雙指針"，b也跳過重復元素
• b每遍歷完一遍，a也跳過重復元素

不漏："雙指針"找到一結果就縮小區間。

五、編寫代碼

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 1.排序sort(nums.begin(), nums.end());// 2.固定數a,固定數b,雙指針算法int n = nums.size();for (int i = 0; i < n; )// 固定數a{// 三數之和for (int j = i + 1; j < n; )// 固定數b{// 雙指針int aim = target - nums[i] - nums[j];int left = j + 1, right = n - 1;while (left < right){int sum = nums[left] + nums[right];if (sum > aim) --right;else if (sum < aim) ++left;else{// 找到一結果就push_back,保證不漏縮小區間ret.push_back({ nums[i], nums[j], nums[left++], nums[right--]});// 去重 left和rightwhile (left < right && nums[left] == nums[left - 1]) ++left;while (left < right && nums[right] == nums[right + 1]) --right;}}// 去重j++j;while (j < n && nums[j] == nums[j - 1]) ++j;}// 去重i++i;while (i < n && nums[i] == nums[i - 1]) ++i;}return ret;}
};

數據范圍溢出的風險，計算的時候可能會超出int的范圍：

可以用long long類型的變量存儲，后面的計算過程只用對第一個數據/第二個數據強制轉換：

long long aim = (long long)target - nums[i] - nums[j];

long long aim = target - (long long)nums[i] - nums[j];

完整代碼：

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 1.排序sort(nums.begin(), nums.end());// 2.固定數a,固定數b,雙指針算法int n = nums.size();for (int i = 0; i < n; )// 固定數a{// 三數之和for (int j = i + 1; j < n; )// 固定數b{// 雙指針long long aim = target - (long long)nums[i] - nums[j];if (nums[i] > 0 && nums[j] > 0 && target < 0) break; int left = j + 1, right = n - 1;while (left < right){int sum = nums[left] + nums[right];if (sum > aim) --right;else if (sum < aim) ++left;else{// 找到一結果就push_back,保證不漏縮小區間ret.push_back({ nums[i], nums[j], nums[left++], nums[right--]});// 去重 left和rightwhile (left < right && nums[left] == nums[left - 1]) ++left;while (left < right && nums[right] == nums[right + 1]) --right;}}// 去重j++j;while (j < n && nums[j] == nums[j - 1]) ++j;}// 去重i++i;while (i < n && nums[i] == nums[i - 1]) ++i;}return ret;}
};

六、時間復雜度和空間復雜度

for循環嵌套for循環嵌套while循環，所以時間復雜度是O(n^3)。

空間復雜度依舊是排序算法占空間，所以空間復雜度是O(logn)。