LeetCode: 15. 三数之和

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

15. 三数之和

给你一个整数数组 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 。

示例 3：

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

提示：

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

解题分析

为什么参考资料中，JS 的代码可以通过，但是转成 Java 之后就不能通过呢？

一刷
二刷
二刷（万能方法）
三刷
四刷

 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
// TODO 还没有通过

/**
 * TODO 还没有通过
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2018-07-19
 */
public static List<List<Integer>> threeSum(int[] nums) {
  if (Objects.isNull(nums) || nums.length < 3) {
    return Collections.emptyList();
  }
  List<List<Integer>> result = new ArrayList<>();
  Arrays.sort(nums);
  if (nums[0] * nums[nums.length - 1] > 0) {
    return result;
  }
  for (int i = 0; i < nums.length - 2 && nums[i] <= 0; ) {
    int left = i + 1, right = nums.length - 1;
    while (left < right && nums[i] * nums[right] <= 0) {
      int sum = nums[i] + nums[left] + nums[right];
      if (sum == 0) {
        result.add(Arrays.asList(nums[i], nums[left], nums[right]));
      }
      if (sum > 0) {
        while (left < right && nums[right] == nums[--right]) {}
      } else {
        while (left < right && nums[left] == nums[++left]) {}
      }
    }
    while (i < nums.length - 1 && nums[i] == nums[++i]) {}
  }
  return result;
}

public static List<List<Integer>> threeSum2(int[] nums) {
  if (nums.length < 3) {
    return new ArrayList<>();
  }
  Set<List<Integer>> result = new HashSet<>();

  Arrays.sort(nums);

  Map<Integer, Integer> numMap = new HashMap<>(nums.length * 4 / 3 + 1);
  for (int i = 0; i < nums.length; i++) {
    numMap.put(nums[i], i);
  }

  if (numMap.size() == 1 && numMap.keySet().contains(0)) {
    result.add(Arrays.asList(0, 0, 0));
    return new ArrayList<>(result);
  }

  for (int i = 0; i < nums.length; i++) {
    for (int j = nums.length - 1; j > i; j--) {
      int minuend = 0 - (nums[i] + nums[j]);
      if (numMap.containsKey(minuend)) {
        Integer k = numMap.get(minuend);
        if (i != k && j != k) {
          int[] oneResult = new int[]{nums[i], nums[j], minuend};
          Arrays.sort(oneResult);
          result.add(Arrays.stream(oneResult).boxed().collect(Collectors.toList()));
        }
      }
    }
  }

  return new ArrayList<>(result);
}

 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
/**
 * 双指针
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-08-15 16:08:08
 */
public List<List<Integer>> threeSum(int[] nums) {
  if (nums == null || nums.length < 3) {
    return Collections.emptyList();
  }
  Arrays.sort(nums);
  List<List<Integer>> result = new ArrayList<>();
  for (int i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) {
      break;
    }
    if (i > 0 && nums[i - 1] == nums[i]) {
      continue;
    }
    int l = i + 1, r = nums.length - 1;
    while (l < r) {
      int sum = nums[i] + nums[l] + nums[r];
      if (sum < 0) {
        while (l < r && nums[l] == nums[++l]) ;
      } else if (0 < sum) {
        while (l < r && nums[r] == nums[--r]) ;
      } else {
        result.add(Arrays.asList(nums[i], nums[l], nums[r]));
        while (l < r && nums[l] == nums[++l]) ;
        while (l < r && nums[r] == nums[--r]) ;
      }
    }
  }
  return result;
}

 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
/**
 * 双指针
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-08-15 16:08:08
 */
public List<List<Integer>> threeSum(int[] nums) {
  if (nums == null || nums.length < 3) {
    return Collections.emptyList();
  }
  Arrays.sort(nums);
  return numSum(nums, 0, 3, 0);
}

private List<List<Integer>> numSum(int[] nums, int idx, int cnt, int target) {
  // 剩余长度不够，则直接返回
  if (nums.length - idx < cnt || cnt < 2) {
    return new ArrayList<>();
  }
  List<List<Integer>> result = new ArrayList<>();
  if (cnt == 2) {
    int l = idx;
    int r = nums.length - 1;
    while (l < r) {
      int sum = nums[l] + nums[r];
      int left = nums[l];
      int right = nums[r];
      if (sum < target) {
        while (l < r && nums[l] == left) {
          l++;
        }
      } else if (target < sum) {
        while (l < r && nums[r] == right) {
          r--;
        }
      } else {
        result.add(new ArrayList<>(Arrays.asList(left, right)));
        while (l < r && nums[l] == left) {
          l++;
        }
        while (l < r && nums[r] == right) {
          r--;
        }
      }
    }
  } else {
    for (int i = idx; i < nums.length; i++) {
      int num = nums[i];
      List<List<Integer>> temp = numSum(nums, i + 1, cnt - 1, target - num);
      for (List<Integer> rs : temp) {
        rs.addFirst(num);
        result.add(rs);
      }
      while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
        i++;
      }
    }
  }
  return result;
}

 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-06 16:53:23
 */
public List<List<Integer>> threeSum(int[] nums) {
  Arrays.sort(nums);
  return numsSum(nums, 0, 3, 0);
}

/**
 * 通用方法，可以处理 count 数之和
 */
private List<List<Integer>> numsSum(int[] nums, int idx, int count, int sum) {
  // 剩余数组长度不够，直接返回
  if (nums.length - idx < count || count < 2) {
    return new ArrayList<>();
  }
  List<List<Integer>> result = new ArrayList<>();
  if (count == 2) {
    int left = idx, right = nums.length - 1;
    while (left < right) {
      int leftNum = nums[left];
      int rightNum = nums[right];
      int iSum = leftNum + rightNum;
      if (iSum == sum) {
        result.add(new ArrayList<>(Arrays.asList(leftNum, rightNum)));
        // 不允许有重复数组，则将重复元素都排除掉
        while (left < right && leftNum == nums[left]) {
          left++;
        }
        while (left < right && rightNum == nums[right]) {
          right--;
        }
      } else if (iSum < sum) {
        while (left < right && leftNum == nums[left]) {
          left++;
        }
      } else {
        while (left < right && rightNum == nums[right]) {
          right--;
        }
      }
    }
    return result;
  } else {
    for (int i = idx; i < nums.length; i++) {
      int num = nums[i];
      // 在这里，递归相当一层循环，无论 count 值多大，就可以通过增加递归次数，来降低 count 的值
      List<List<Integer>> lists = numsSum(nums, i + 1, count - 1, sum - num);
      for (List<Integer> list : lists) {
        list.add(num);
        result.add(list);
      }
      // 不允许有重复数组，则将重复元素都排除掉
      // 使用 nums[i] == nums[i + 1] 来判断，因为执行完该语句之后，还有一个 i++ 要执行
      while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
        i++;
      }
    }
  }
  return result;
}

 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
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-03-06 16:53:23
 */
public List<List<Integer>> threeSum(int[] nums) {
  Arrays.sort(nums);
  return numSum(nums, 0, 3, 0);
}

private List<List<Integer>> numSum(int[] nums, int idx, int cnt, int target) {
  // 剩余数组长度不够，直接返回
  if (nums.length - idx < cnt || cnt < 2) {
    return new ArrayList<>();
  }
  if (cnt > 2) {
    List<List<Integer>> result = new ArrayList<>();
    while (idx < nums.length) {
      int in = nums[idx];
      if (in > target) {
        break;
      }
      // 利用递归推进下标前进，这样多少个数的sum都可以处理
      List<List<Integer>> temp = numSum(nums, idx + 1, cnt - 1, target - in);
      for (List<Integer> res : temp) {
        res.add(in);
        result.add(res);
      }
      // 不允许有重复数组，则跳过重复元素
      while (idx < nums.length && in == nums[idx]) {
        idx++;
      }
    }
    return result;
  } else {
    List<List<Integer>> result = new ArrayList<>();
    int l = idx, r = nums.length - 1;
    while (l < r) {
      int ln = nums[l];
      if (target < ln) {
        break;
      }
      int rn = nums[r];
      int sum = ln + rn;
      if (sum == target) {
        result.add(new ArrayList<>(Arrays.asList(ln, rn)));
        // 跳过重复元素
        while (l < r && nums[l] == ln) {
          l++;
        }
        while (l < r && nums[r] == rn) {
          r--;
        }
      } else if (sum < target) {
        // 跳过重复元素
        while (l < r && nums[l] == ln) {
          l++;
        }
      } else {
        // 跳过重复元素
        while (l < r && nums[r] == rn) {
          r--;
        }
      }
    }
    return result;
  }
}

参考资料

15. 三数之和 - 三数之和题解