【leetcode】三数之和

一、题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] +
nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。

二、代码思路

本题是二数之和的进阶，思路与二数之和一致，使用双指针来找出两个数之和为target的两个数。

为什么要使用双指针？

其实题目中并非只用双指针，而是用了排序＋双指针，首先，枚举 i，确定target，然后题目就转换成找到 k 和 j 两个元素与i不同，同时k与j也不相同的两个数之和变为target。

由此，我们能看出三数之和也就是两数之和，只不过加了一些限制条件，就是 i j k 两两不等。

双指针的优势是什么？

直白的说双指针针对暴力解法降低了一层时间复杂度，如果我们使用暴力解法，那么通过两层for循环枚举出所有的两个数的组合，时间复杂度为n2，但是双指针只需要一个for循环即可。

如何进行双指针的走动？

我们可以首先对数组进行排序，然后通过双指针代表的两个元素之和，与target相比较，如果sum > target 那么右指针移动，反之亦然。

总结：

• 双指针可以减低复杂度。
• 双指针由明显的解题特点。
• 双指针的难度是如何确定左右指针的移动。

三、代码题解

package leetcode.lc20221204;

import java.util.*;

/*
 * @author lzy
 * @version 1.0
 * */
public class Solution02 {
    public static void main(String[] args) {
        Solution02 solution02 = new Solution02();
        solution02.threeSum(new int[]{-1,0,1,0});
    }

    public List<Integer> placeElement(int i, int j, int k, int[] nums, List<Integer> temp) {
        temp.add(nums[i]);
        temp.add(nums[j]);
        temp.add(nums[k]);
        return temp;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        //边界值判断
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Set<List<Integer>> set = new HashSet<>();
        int length = nums.length;
        if (length == 3) {
            int sum = nums[0] + nums[1] + nums[2];
            if (sum == 0) {
                list.add(nums[0]);
                list.add(nums[1]);
                list.add(nums[2]);
                res.add(list);
                return res;
            } else {
                return new ArrayList<>();
            }
        }
        //其他判断,匿名内部类写法
        Integer[] array = new Integer[length];
        int count = 0;
        for (int i : nums) {
            array[count++] = new Integer(i);
        }
        Arrays.sort(array, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        Arrays.sort(nums);
        //两数之和的进阶，但是思路一致
        //首先，确定一个数
        for (int i = 0; i < length; i++) {
            //其次，按照两数之和的思路确定另外两个数, 注意需要把数组先排好序
            int left = 0;
            int right = length - 1;
            int target = -nums[i];
            while (left < right) {
                //不能和i相等
                if (left == i) {
                    left++;
                } else if (right == i) {
                    right--;
                }
                if (left == right) {
                    break;
                }
                int sum = nums[left] + nums[right];
                List<Integer> temp = new ArrayList<>();
                if (sum == target) {
                    //输出结果集的时候要考虑不能重复
                    if (i < left) {
                        placeElement(i, left, right, nums, temp);
                    } else if (i > right) {
                        placeElement(left, right, i, nums, temp);
                    } else {
                        placeElement(left, i, right, nums, temp);
                    }
                    set.add(temp);
                    //相等之后移动谁都无所谓,因为结果要不重复的结果集
                    left++;
                } else if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                }
            }
        }
        return new ArrayList<>(set);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94