题目描述

三数之和

代码解析

暴力

在做这一道题的时候，脑海里先想出来的是暴力方法，一次排序，将这个数组变为有序的，再通过三次for循环来寻找满足条件的数字，然后将符合条件的数组与之前符合条件的数组进行一一对比，来完成去重的目的，时间复杂度光是三层for循环就达到了n^3，再加上一个sort和count函数，nlogn + mn^3。

class Solution {
public:bool chech(int a, int b, int c){return a + b + c == 0;}vector<vector<int>> threeSum(vector<int>& na) {vector<vector<int>> ans;int n = na.size();sort(na.begin(), na.end());for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){for (int k = j + 1; k < n; k++){if (chech(na[i], na[k], na[j])){vector<int> a(3, 0);a[0] = na[i];a[1] = na[j];a[2] = na[k];if (count(ans.begin(), ans.end(), a) == 0)ans.push_back(a);}}}}return ans;}
};

---

优化

这个时候要想代码如何进行优化，如何把判重的count和后两层循环给优化了，这样就能把时间复杂度从nlogn + mn^3降低到nlogn + n^2。

要找一个满足条件的三个数，我们可以先固定一个数字，然后就可以只考虑除固定数字之外的区间了，在另一个区间可以找两个指针l和r，如果说l指针指向的数字+r指针指向的数字，等于 事前固定的数字的相反数，就可以达到题目要求了。

如果说l+r > -i，说明r太大，r--；或者说是r + l > -i，说明l太小，l++。当l和r相交的时候依旧没有找到答案，就说明i在某个固定的位置是没有解的，将i++，即可。然后继续在l和r区间寻找符合题意的数字。

题目要求不能有重复的，什么情况下会出现重读的？当l + r == -i的时候，l的下一位或者r的上一位跟l或r本身是相同的，就说明出现了重复的情况，也有可能是i跟i的下一位相同。所以可以以此为条件，来进行去重。也可以将所有符合题意的答案都加入到一个数组当中，然后使用去重算法，也可以达到去重的目的。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();sort(nums.begin(), nums.end());vector<vector<int>> res;for (int i = 0; i < n;){if (nums[i] > 0) break;int l = i + 1, r = n - 1;int t = -nums[i];while (l < r){int sum = nums[l] + nums[r];if (sum > t) r--;else if (sum < t) l++;else {res.push_back({nums[l], nums[r], nums[i]});l++, r--;while (l < r && nums[l] == nums[l - 1]){l++;}while (l < r && nums[r] == nums[r + 1]) {r--;}}}i++;while (i < n && nums[i] == nums[i - 1]) i++;}return res;}
};

 

扩展

四数之和

四数之和和三数之和的代码类似，可以当练习做一下。 

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int n = nums.size();vector<vector<int>> res;sort(nums.begin(), nums.end());for (int i = 0; i < n ; ){for (int j = i + 1; j < n; ){int l = j + 1;int r = n - 1;long long tmp = nums[i] + nums[j];long long t = target - tmp;while (l < r){if ((long long)(nums[l] + nums[r]) > t) r--;else if ((long long)(nums[l] + nums[r]) < t) l++;else {res.push_back({nums[i], nums[j], nums[l], nums[r]});l++;r--;while (l < r && nums[l] == nums[l - 1]){l++;}while (l < r && nums[r] == nums[r + 1]) {r--;}}}j++;while (j < n && nums[j] == nums[j - 1]) j++;}i++;while (i < n && nums[i] == nums[i - 1]) i++;}return res;}
};