[NC]54. 数组中相加和为 0 的三元组

🚩传送门：牛客题目

题目

给出一个有 个元素的数组，中是否有元素 满足 找出数组中所有满足条件的三元组。

注意：

1. 三元组中的元素必须按非降序排列。（即）
2. 解集中不能包含重复的三元组。

示例 1：

输入：[-10,0,10,20,-10,-40] 输出：[[-10,-10,20],[-10,0,10]]

解题思路：双指针

1. 首先对数组进行排序（从小到大）
2. 依次取出数组中的每个数作为 ，并且不重复的选取（跳过重复的数）
3. 这样问题就转换为 _2_ 个数求和的问题（可以用双指针解决方法）
   • 则 **_right-- _**
   • 则 **_left++_**
   • 则 **_right--，left++_**（跳过重复的数）

官方代码

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) break;    // 因为排序后 nums[j] >= nums[i] >= nums[i] > 0
            if (i > 0 && nums[i] == nums[i - 1]) continue;    // target去重 
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                    while (left < right && nums[left] == nums[++left]) ;
                    while (left < right && nums[right] == nums[--right]) ;
                }
            }
        }
        return res;
    }
}