题目
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
1 2 3 4 5 6 7
| 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
|
思路+代码
先排序,然后三数之和等于零必定有 1 到 2 个小于零, 1 到 2 个大于零。
然后我们采用双指针,先固定最小的一个数(负值);然后双指针再后面区间寻找两个数,与前面数相加等于零。
注意:因为不能包含重复三元组,在遍历过程中注意去重。保证每次遍历的数字与前面不一样即可(因为排序了)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<List<Integer>>(); Arrays.sort(nums); int len = nums.length; for(int i=0; i<len; i++){ if(nums[i]>0) break; if(i>0 && nums[i]==nums[i-1]) continue; int j=i+1; int k=len-1; while(j<k){ if(nums[j]+nums[k]==-nums[i]){ ArrayList<Integer> list = new ArrayList<Integer>(); list.add(nums[i]); list.add(nums[j]); list.add(nums[k]); res.add(list); while(j<k&&nums[j]==nums[j+1]){ j++; } while(j<k&&nums[k]==nums[k-1]){ k--; } j++; k--; }else if(nums[j]+nums[k]<-nums[i]){ j++; }else{ k--; } } } return res; } }
|
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。