题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/1fGaJU 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

首先是暴力求解法，但效率肯定低，有没有什么办法更好呢？
其实最关键的在于，如何搜索判断不重复？

方法一：
我设立 A B C 三个数在滑动
A从1 B从2 C从3
AB固定，C滑动搜索，
C搜索完一组，B向后滑动一位，C顺位向后搜索
然后就是A向后滑动
这种有剪枝的搜索判断

方法二：
但是实际上感觉还有可以优化的空间，因为你在前面搜索的时候，就其实已经遇到了所有的数字，
那么，能不能在搜索的过程中，利用哈希表的思想，保存已出现的数字和个数，一旦发现缺哪个数字，就去找一下这个数，如果这个数字位置不重复，那么就找到了一组

先遍历一遍，统计出现的数字和出现的次数
然后问题转换为，我取出一个数，去看剩下的组合里是否能出现相加和为 -a的数的组合

其他人的思路：
先排序一遍，保证数组有序
然后后面的思路和我的差不多

代码实现：

方法一：排序后暴力求解

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) {
  4.         int len = nums.size();
  5.         vector<vector<int>> ans;
  6.         if(len<=2) return ans;
  7.         sort(nums.begin(),nums.end());
  8.         for(int a=0;a<len-2;a++){
  9.             if(a>0&&nums[a]==nums[a-1]) continue;
  10.             int A = nums[a];
  11.             //去寻找剩下的里面有没有和为-A的两个数
  12.             for(int b=a+1;b<len-1;b++){
  13.                 if(b>a+1&&nums[b]==nums[b-1]) continue;
  14.                 for(int c = b+1;c<len;c++){
  15.                     if(c>b+1&&nums[c]==nums[c-1]) continue;
  16.                     if(nums[c]+nums[b]==-A){
  17.                         vector<int> tmp_ans;
  18.                         tmp_ans.push_back(nums[a]);
  19.                         tmp_ans.push_back(nums[b]);
  20.                         tmp_ans.push_back(nums[c]);
  21.                         ans.push_back(tmp_ans);
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.         return ans;
  27.     }
  28. };

这玩意超时了。。。。。

方法二：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) {
  4.         if (nums.size() < 3) return {};
  5.         vector<vector<int>> res;
  7.         sort(nums.begin(), nums.end());
  8.         for (int i = 0; i < nums.size() - 2; i++) {
  9.             if (i > 0 && nums[i] == nums[i - 1]) continue;
  11.             // 在 i + 1 ... nums.length - 1 中查找相加等于 -nums[i] 的两个数
  12.             int target = - nums[i];
  13.             int left = i + 1, right = nums.size() - 1;
  14.             while (left < right) {
  15.                 int sum = nums[left] + nums[right];
  16.                 if (sum == target) {
  17.                     res.push_back({nums[i], nums[left], nums[right]});
  18.                     /*
  19.                         下面的代码相当于：
  20.                         while (left < right) {
  21.                             // 不管前后相不相等，left 都要往前走
  22.                             left++;
  23.                             if (nums[left - 1] != nums[left]) break;
  24.                         }
  25.                         while (left < right) {
  26.                             // 不管前后相不相等，right 都要往后走
  27.                             right--;
  28.                             if (nums[right + 1] != nums[right]) break;
  29.                         }
  30.                      */
  31.                     // 去重
  32.                     while (left < right && nums[left] == nums[++left]);
  33.                     while (left < right && nums[right] == nums[--right]);
  34.                 } else if (sum < target) {
  35.                     left++;
  36.                 } else {
  37.                     right--;
  38.                 }
  39.             }
  40.         }
  41.         return res;
  42.     }
  43. };

这个方法在寻找另外两个数的时候，利用了双指针，

复杂度分析

时间：排序O（nlogn）+双指针查找O(n)

空间：O(n)