1.题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
2.样例描述
3.思路描述
先将 nums 排序，时间复杂度为 O(NlogN)O(NlogN)O(NlogN)。
固定 333 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端。
双指针 iii , jjj 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：
当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 333 个元素都大于 000 ，在此固定指针 k 之后不可能再找到结果了。
当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
i，j 分设在数组索引 (k,len(nums))(k, len(nums))(k,len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
当s < 0时，i += 1并跳过所有重复的nums[i]；
当s > 0时，j -= 1并跳过所有重复的nums[j]；
当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。（思路来源于网络高手@krahets）
4.代码展示
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; // 定义两个指针，i从k的下一个位置开始，j从数组末尾开始int i = k + 1, j = nums.length - 1; // 内层循环，使用双指针法找到三元组while (i < j) {int sum = nums[k] + nums[i] + nums[j]; // 如果三元组的和小于零，移动i指针，直到遇到不同的元素if (sum < 0) {while (i < j && nums[i] == nums[++i]);} // 如果三元组的和大于零，移动j指针，直到遇到不同的元素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])));// 移动i和j指针，跳过相邻相等的元素while (i < j && nums[i] == nums[++i]);while (i < j && nums[j] == nums[--j]);}}}// 返回结果列表return res;}
}
