目录

题目

思路

代码

---

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路

这道题的关键在于去重

用哈希表写有很多去重细节，难以一次到位

所以采用双指针法

先把这个数组排序（从小到大），用i遍历数组中每一个数字，left指向i+1，right指向length-1，然后三个数相加，如果等于0， 那么添加，如果大于0，那么right--；如果小于0，那么left++。

接下来是去重的问题

 对于a的去重，是要判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同？

 如果和他的后一个比较，那么会把三元组中只要有两个数字相同的结果集去掉，比如{-1, -1 ,2}，符合要求，但是会被去掉，所以不能和后一个比较

不能有重复的三元组，但三元组内的元素是可以重复的！

我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。

对b和c去重也是类似的思路

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result=new ArrayList<>();//创建一个二维数组Arrays.sort(nums);//排序for(int i=0;i<nums.length;i++){if(nums[i]>0){//当第一个数都待遇0，那么没有符合要求的，直接返回return result;}if(i>0&&nums[i]==nums[i-1]){//去重continue;}int left=i+1;int right=nums.length-1;while(right>left){int sum=nums[i]+nums[left]+nums[right];if(sum>0) {right--;}else if(sum<0){left++;}else{result.add(Arrays.asList(nums[i], nums[left], nums[right]));//符合条件，添加while(right>left&&nums[right]==nums[right-1]){right--;}while(right>left&&nums[left]==nums[left+1]){left++;}left++;right--; }}}return result;}
}