题目描述
输入参数：
- 有限数量元素的整数数组 0 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
题目逻辑：
- 找到数组中三个整数a、b、c，使得a+b+c=0的三元组
输出结果：
- 返回多个个三元组
特别说明：
- 注意：答案中不可以包含重复的三元组。
题目示例
示例 1
输入：[1,2,3,4,5] 输出：[] 复制代码
示例 2：
输入：[-1,0,1,2,-1,-2] 输出：[[-1,0,1],[-1,-1,2],[-2,0,2]] 复制代码
示例 3：
输入：nums = [] 输出：[] 复制代码
示例 3：
输入：nums = [0] 输出：[] 复制代码
思路分析
排序 + 双指针
- 首先对数组进行排序，排序后固定一个数nums[i]，再使用左右指针指向nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 00，满足则添加进结果集。
- 如果 nums[i]大于 00，则三数之和必然无法等于 00，结束循环。
- 如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过。
- 当 sum == 00 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
- 当 sum == 00 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
- 当 sum == 00 时，即使 nums[L] <> nums[L+1] 且 nums[R] <> nums[R−1]
也需要进行相关的 L++ 和 R--。
AC代码
实现方法1
class Solution { public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList(); int len = nums.length; if(nums == null || len < 3) return ans; Arrays.sort(nums); // 排序 for (int i = 0; i < len ; i++) { // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 if(nums[i] > 0) break; if( i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i+1; int R = len-1; while(L < R){ int sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.add(Arrays.asList(nums[i],nums[L],nums[R])); while (L<R && nums[L] == nums[L+1]) L++; // 去重 while (L<R && nums[R] == nums[R-1]) R--; // 去重 L++; R--; } else if (sum < 0) L++; else if (sum > 0) R--; } } return ans; } } 复制代码
实现方法2
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); for(int k = 0; k < nums.length - 2; k++){ if(nums[k] > 0) break; if(k > 0 && nums[k] == nums[k - 1]) continue; int i = k + 1, j = nums.length - 1; while(i < j){ int sum = nums[k] + nums[i] + nums[j]; if(sum < 0){ while(i < j && nums[i] == nums[++i]); } else if (sum > 0) { while(i < j && nums[j] == nums[--j]); } else { res.add(new ArrayList<Integer> (Arrays.asList(nums[k], nums[i], nums[j]))); while(i < j && nums[i] == nums[++i]); while(i < j && nums[j] == nums[--j]); } } } return res; } } 复制代码
总结：
借鉴算法1：leetcode-cn.com/problems/3s…
借鉴算法2：leetcode-cn.com/problems/3s…
