给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
1 public class T15 { 2 public List<List<Integer>> threeSum(int[] nums) { 3 List<List<Integer>> lists = new ArrayList<>(); 4 5 if (nums == null || nums.length < 3) { 6 return lists; 7 } 8 9 Arrays.sort(nums); 10 for (int i = 0; i < nums.length - 2; i++) { 11 List<Integer> list = new ArrayList<>(); 12 if (nums[i] > 0) { 13 break; 14 } 15 if (i > 0 && nums[i] == nums[i - 1]) { 16 continue; 17 } 18 int l = i + 1, r = nums.length - 1; 19 while (l < r) { 20 int sum = nums[l] + nums[i] + nums[r]; 21 if (sum == 0) { 22 list.add(nums[i]); 23 list.add(nums[l]); 24 list.add(nums[r]); 25 while (l < r && nums[l] == nums[l +1]) { 26 l++; 27 } 28 while (l < r && nums[r] == nums[r - 1]) { 29 r--; 30 } 31 l++; 32 r--; 33 } else if (sum > 0) { 34 r--; 35 } else { 36 l++; 37 } 38 } 39 lists.add(list); 40 } 41 return lists; 42 } 43 }