三数之和


题目描述

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

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

示例:

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

题解

之前做过两数之和这道题,所以第一想法就是转化成两次两数之和解决,思路就是先求 b + c 两数之和 z,再求 a + z 两数之和等于0,也就是相反数。

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
 public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// 求出两数之和的组合,和为-nums[i]
List<List<Integer>> twoSumList = twoSum(nums, i + 1, -nums[i]);
for (List<Integer> list : twoSumList) {
list.add(nums[i]);
Collections.sort(list);
result.add(list);
}
}
return result.stream().distinct().collect(Collectors.toList());
}

public List<List<Integer>> twoSum(int[] nums, int index, int target) {
Map<Integer, Integer> map = new HashMap<>();
List<List<Integer>> result = new ArrayList<>();
for (int i = index; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = index; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[map.get(complement)]);
result.add(list);
// 去重,防止重复执行超时
map.remove(nums[i]);
map.remove(complement);
}
}
return result;
}

其实这道题有更好的解法,受之前两数之和的影响,两数之和的那道题,是没法给数组排序的,因为输出是数组下标,而这道题,输出是三元组,可以进行数组排序的,以下是来自LeetCode的题解:

  • 首先对数组进行排序,排序后固定一个数 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−−。

    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
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    int len = nums.length;
    if (nums == null || len < 3)
    return res;
    Arrays.sort(nums);
    for (int i = 0; i < len; i++) {
    if (nums[i] > 0)
    break; // 如果当前数字大于0,则三数之和一定大于0,所以结束循环
    if (i > 0 && nums[i] == nums[i - 1])
    continue; // 去重
    int L = i + 1;
    int R = len - 1;
    while (L < R) {
    int sum = nums[i] + nums[L] + nums[R];
    if (sum == 0) {
    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
    while (L < R && nums[L] == nums[L + 1])
    L++; // 去重
    while (L < R && nums[R] == nums[R - 1])
    R--; // 去重
    L++;
    R--;
    } else if (sum < 0)
    L++;
    else if (sum > 0)
    R--;
    }
    }
    return res;
    }

来源

三数之和 | 力扣(LeetCode)
三数之和 | 题解(LeetCode)


文章标题:三数之和
文章作者:cylong
文章链接:http://www.cylong.com/blog/2020/05/30/three-sum/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)