三数之和

---

题目描述

给你一个包含 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，也就是相反数。

 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−−。

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
文章链接：https://0skyu.cn/posts/419e.html
有问题或者建议欢迎在下方评论。欢迎转载、引用，但希望标明出处，感激不尽(●’◡’●)