三数之和

难度中等

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

示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]]

在看这个问题之前可以先看下 两数之和

当碰到这个三数之和的时候，首先想到的思路就是既然 a + b = c ，那么 a + b = -c，我在想，是不是可以以这个 -c 为 target ，然后迭代数组，重用这个两数之和的方法？代码如下：

public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        HashSet<List<Integer>> set = new HashSet<>();
        for(int i = 0;i<nums.length;i++){
            List<List<Integer>> res = twoSum(nums,-nums[i],i);
            if(res != null && res.size() != 0){
                for(List<Integer>  l : res) {
                    //将适合的数对与当前数组合起来然后去重！！！
                    int[] arr = new int[]{nums[i], l.get(0), l.get(1)};
                    Arrays.sort(arr); //通过排序进行去重！！！
                    List<Integer> list1 = new ArrayList<>();
                    list1.add(arr[0]);
                    list1.add(arr[1]);
                    list1.add(arr[2]);
                    if (!set.contains(list1)) {
                        set.add(list1);
                    }
                }
            }
        }
        List list2 = new ArrayList(set);
        System.out.println(list2.toString());
        return list2;
    }
    public List<List<Integer>> twoSum(int[] nums, int target ,int j){
        //两数之和，返回所有和为目标和的数对！！！注意 传入的本位 j 应该跳过！！！ 
        HashSet<Integer> hashSet = new HashSet<>();
        List<List<Integer>> list = new ArrayList<>();
        for(int i = 0;i<nums.length;i++){
            if(i == j){
                continue;
            }
            if(hashSet.contains(target - nums[i])){
                List<Integer> l = new ArrayList<>();
                l.add(nums[i]);
                l.add(target - nums[i]);
                list.add(new ArrayList<>(l));
            }
            hashSet.add(nums[i]);
        }
        return list;
    }

结果

超时了。。。。。。。找出合适的数对的时间复杂度就 O(n ^ 2)，然后又通过排序进行去重，整体的时间复杂度固然很高

最佳思路

排序加双指针

首先因为所求为三个数之和为0，不需要求下标，所以可以对数组进行排序，使得整体具有规律性！其实两数之和也可以通过排序加双指针，但是那个题所求为下标，不能打乱数组，所以最好的就是用哈希表。一旦排好序之后，就可以用上面的思路了，即将每个数作为 target，然后遍历剩下的数，进行判断！
其实这里边有很多技巧，可以仔细通过代码体会：

public List<List<Integer>> threeSum1(int[] nums) {
        if(nums == null || nums.length <= 2){
            return new ArrayList<>();
        }
        List<List<Integer>> res_list = new ArrayList<>();
        int len = nums.length;
        int left = -1;
        int right = -1;
        Arrays.sort(nums); //排序是前提！！！使其有序之后，才可以通过一些条件加速过程
        for(int i = 0;i < len;i++){
            if(nums[i] > 0){
                //如果当前位置大于零，说明之后的都大于零，一定不可能凑出三个数使得 a + b + c = 0！
                break;
            }
            if(i >= 1 && nums[i] == nums[i -1]){
                //如果当前数字等于前一个数字，说明是重复的，没必要在进行之后判断！
                continue;
            }
            left = i + 1; //从后面一个数字开始即可！
            right = len - 1;
            while(left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res_list.add(list);
                    left++;
                    right--;
                    //以下两个while循环为去重过程
                    while (left < right &&nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while(left < right && nums[right] == nums[right + 1]){
                        right --;
                    }
                }else if(sum > 0){
                    right --;
                }else{
                    left ++;
                }
            }
        }
        return res_list;
    }

本作品采用《CC 协议》，转载必须注明作者和本文链接