3Sum 三数之和

问题描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

$3 <= nums.length <= 3000\\\ -10^5 <= nums[i] <= 10^5$

分析

需要找出所有和为0 ，但是又不能重复的三元组。
也就是说一个有效的三元组，x+y+z=0，并且下标不一样。
而且还需要不能重复。

最朴素的方式就是暴力，可以枚举出所有符合条件的组合，然后去重，或者是在过程中去重。

而最容易联想到的就是2sum，固定x，枚举yz，时间复杂度 $O(N^3)$ ,去重的时间和空间开销还没算进去。

该策略太暴力，容易实现，但是时间复杂度太高无法快速得到结果。

基于2sum中的双指针，可以在 $O (N)$ 的时间复杂度下找到2个元素.

所以可以尝试固定x，然后使用双指针的方式找到yz,时间复杂度 $O(N^2)$ 。
这个思路明显由于上面的暴力，但是还有一个问题没有解决，就是重复。

在使用双指针策略之前，首先要做的就是sort。

之所以重复，就是在无序的状态下，可能会找到一组xyz，然后又找到了yxz，这就产生了重复。

因此在这个过程中，依然是固定x，但是x只能使用一次，同时要确保组合中的x<=y<=z。

这样一个x，可能会找到多组的yz,但是组合不会重复。

代码

 public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new        ArrayList<List<Integer>>();if(nums == null || nums.length<3){return result;}Arrays.sort(nums);for(int i=0; i<nums.length-2; i++){if(i==0 || nums[i] > nums[i-1]){int j=i+1;int k=nums.length-1;while(j<k){if(nums[i]+nums[j]+nums[k]==0){List<Integer> l = new ArrayList<Integer>();l.add(nums[i]);l.add(nums[j]);l.add(nums[k]);result.add(l);    j++;k--; while(j<k && nums[j]==nums[j-1]){j++;}while(j<k && nums[k]==nums[k+1]){k--;}}else if(nums[i]+nums[j]+nums[k]<0){j++;}else{k--;}}}    }return result;}