题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

样例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

算法分析

排序 + 双指针

• 1、枚举每个数，表示该数nums[i]已被确定，在排序后的情况下，通过双指针l，r分别从左边l = i + 1和右边n - 1往中间靠拢，找到nums[i] + nums[l] + nums[r] == 0的所有符合条件的搭配
• 2、在找符合条件搭配的过程中，假设sum = nums[i] + nums[l] + nums[r]
  • 若sum > 0，则r往左走，使sum变小
  • 若sum < 0，则l往右走，使sum变大
  • 若sum == 0，则表示找到了与nums[i]搭配的组合nums[l]和nums[r]，存到ans中
• 3、判重处理
  • 确定好nums[i]时，l 需要从i + 1开始
  • 当nums[i] == nums[i - 1]，表示当前确定好的数与上一个一样，需要直接continue
  • 当找符合条件搭配时，即sum == 0,需要对相同的nums[l]和nums[r]进行判重出来

时间复杂度 $O(n^2)$

Java 代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        Arrays.sort(nums);
        //确定第一个数
        for(int i = 0;i < n ;i ++)
        {
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1,r = n - 1;

            while(l < r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum > 0) 
                {
                    r --;
                    continue;
                }
                if(sum < 0)
                {
                    l ++;
                    continue;
                }
                //sum == 0时
                ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
                //去除重复处理
                do {l ++;} while(l < r && nums[l] == nums[l - 1]);
                do {r --;} while(l < r && nums[r] == nums[r + 1]);
            }

        }
        return ans;
    }
}