15. 三数之和(一般)

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

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

示例：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

思路：

排序+双指针

  • 首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
  • 如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
  • 如果 nums[i] == nums[i-1]，则说明该数字重复，会导致结果重复，所以应该跳过
  • 当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
  • 当 sum == 0 时，nums[R] == nums[R-1] 则会导致结果重复，应该跳过，R−−
    时间复杂度：O(n^2)，n 为数组长度

思路2：

哈希 未写

代码：

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
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //左右指针，先排序，然后固定nums[i],在i后面左右找
        int len = nums.length;
        Arrays.sort(nums);//排序
        List<List<Integer>> list = new ArrayList<>();
        for(int i=0;i<len;i++){
            //如果i对应值大于0，后面肯定也大于0，不用找了，直接false
            if(nums[i]>0) break;
            //如果和前面数一样,跳过
            if(i>0&&nums[i]==nums[i-1]) continue;
            int left = i+1;
            int right = len-1;
            while(left<right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum==0){
                    //找到了，将这三个数加入数组
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //这里还要去重，注意了，这里
                    while(left<right && nums[left]==nums[left+1]) left++;
                    while(left<right && nums[right-1]==nums[right]) right--;
                    //添加完，指针还是要移动的
                    left++;
                    right--;
                }else if(sum<0)
                    left++;
                else if(sum>0)
                    right--;
            }
        }
        return list;
    }
}


class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        //特别判断
        if(nums==null || nums.length<3){
            return res;
        }
        //首先对数组进行排序，可以将重复值集中到一起，便于去重
        Arrays.sort(nums);
        //双指针
        for(int i=0;i< nums.length-2;i++){
            //如果第一个数大于0，后面都会比它大，肯定不会成立
            if(nums[i]>0){
                break;
            }
            //第一个数去重
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            //双指针
            int left = i+1;
            int right = nums.length-1;

            int target = -nums[i];
            while(left<right){
                //如果找到
                if(nums[left]+nums[right]==target){
                    res.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
                    //++--,但注意还得去重
                    left++;
                    right--;
                    //第二个数去重
                    while (left<right && nums[left]== nums[left-1]){
                        left++;
                    }
                    //第三个数去重
                    while (left<right && nums[right]== nums[right+1]){
                        right--;
                    }
                }else if(nums[left]+nums[right]<target){
                    left++;
                }else {
                    right--;
                }
            }

        }
        return res;
    }
}