本文共 1732 字，大约阅读时间需要 5 分钟。
给你一个包含 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]输出：[]
提示：
0 <= nums.length <= 3000-105 <= nums[i] <= 105
如果使用三重循环来枚举每种情况，则时间复杂度为O(N3)。
另外题中还要求答案中不可以包含重复的三元组。虽然可以使用哈希表来进行去重操作，但是这样又大大消耗了空间，而且操作起来相当的不方便，我们可以想到先将数组排好序，这样相同的元素就可以保持相邻。另外，在我们枚举的三元组 (a, b, c)满足 a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，而(b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。Arrays.sort(nums);for(int i=0;i
对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。
而对于三重循环，我们可以固定一个指针a,然后从a的后面两端来枚举b和c，即从小到大枚举b,从大到小枚举c。这样就可以保持第二重循环不变，第三重循环变成一个从数组最右端开始向左移动的指针 当我们需要枚举数组中的两个元素时，如果我们发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 O(N^2) 减少至 O(N)。为什么是 O(N)呢？这是因为在枚举的过程每一步中，「左指针」会向右移动一个位置（也就是题目中的 bb），而「右指针」会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 O(N)，均摊下来，每次也向左移动一个位置，因此时间复杂度为 O(N)。class Solution { private List > lists; public List > threeSum(int[] nums) { lists=new ArrayList >(); //如果数组长度小于3，无法满足有三个数，直接返回空集 if(nums.length<3){ return lists; } Arrays.sort(nums); int len=nums.length; for(int i=0;i 0){ break; } //避免重复 if(i!=0 && nums[i]==nums[i-1]){ continue; } //定义双指针 int j=i+1; int k=len-1; int prej=-1; //prej为了去除j指针所指的元素的重复情况 while(j 0){ k--; //如果三数之和小于0，那么j++ }else if((nums[j]+nums[k]+nums[i])<0){ j++; //如果三数之和等于0 }else if((nums[j]+nums[k]+nums[i])==0){ //当该数在之前已经被枚举到了，仅移动指针 if(prej!=-1 && nums[j]==nums[prej]){ k--; j++; continue; }else{ //如果没有，就添加到集合中，并标记这一次成功枚举时的指针j的位置 List list=new ArrayList (); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); lists.add(list); prej=j; } k--; j++; } } } return lists; }}
转载地址：http://shgyk.baihongyu.com/