三数之和

---

题目描述

给你一个包含 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）

---