【LeetCode 题解】算法：15.三数之和

一、问题描述

在 LeetCode 上有这样一道经典的算法题，题目要求给定一个整数数组 nums，找出所有不重复的三元组 [nums[i], nums[j], nums[k]]，需要满足以下两个条件：

三个元素的索引互不相同，即 i != j，i != k，j != k。
这三个元素的和为 0，也就是 nums[i] + nums[j] + nums[k] == 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[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。

二、思路分析

暴力法（不可取）

暴力法的思路是尝试数组中所有可能的三元组组合。对于一个长度为 n 的数组，需要三层嵌套循环来遍历所有组合，其时间复杂度为 O(n3)。当数组规模较大时，这种方法的效率极低，会导致程序运行时间过长，因此在实际应用中不可行。

哈希表法（有优化空间但较复杂）

此方法的思路是先遍历数组中的每个元素 nums[i]，将问题转化为在剩余元素中寻找两数之和为 -nums[i] 的问题。可以使用哈希表来记录元素及其出现的位置，这样在查找互补元素时可以将时间复杂度从 O(n) 降低到 O(1)。整体时间复杂度为 O(n2)。不过，使用哈希表法需要处理重复元素的问题，实现起来相对复杂。

排序 + 双指针法（最优解）

这是解决该问题的最优方案，步骤如下：

排序数组：对数组进行排序，排序后相同的元素会相邻排列，这便于后续跳过重复元素，减少不必要的计算。
固定第一个数：依次选取数组中的每个元素作为三元组的第一个数。
双指针查找：在剩余的元素中使用双指针，一个指针从第一个数的下一个元素开始向右移动，另一个指针从数组的最后一个元素开始向左移动，通过移动指针来寻找满足和为 0 的另外两个数。
时间复杂度：排序的时间复杂度为 O(nlogn)，双指针查找的时间复杂度为 O(n2)，因此总的时间复杂度为 O(n2)，该方法适合处理较大规模的数据。

三、详细解题代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class ThreeSum {public static List<List<Integer>> threeSum(int[] nums) {// 用于存储最终结果的列表List<List<Integer>> result = new ArrayList<>();// 首先检查数组长度，如果小于 3，直接返回空列表if (nums == null || nums.length < 3) {return result;}// 对数组进行排序，方便后续去重和双指针操作Arrays.sort(nums);int n = nums.length;// 遍历数组，固定第一个数for (int i = 0; i < n; i++) {// 如果当前数大于 0，由于数组已排序，后面的数都大于 0，不可能找到和为 0 的三元组，直接跳出循环if (nums[i] > 0) {break;}// 跳过重复的第一个数if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 初始化双指针，j 指向 i 的下一个元素，k 指向数组末尾int j = i + 1;int k = n - 1;// 双指针查找满足条件的另外两个数while (j < k) {int total = nums[i] + nums[j] + nums[k];if (total == 0) {// 找到满足条件的三元组，添加到结果列表中result.add(Arrays.asList(nums[i], nums[j], nums[k]));// 跳过重复的第二个数while (j < k && nums[j] == nums[j + 1]) {j++;}// 跳过重复的第三个数while (j < k && nums[k] == nums[k - 1]) {k--;}// 移动指针继续寻找j++;k--;} else if (total < 0) {// 总和小于 0，说明需要增大和，将左指针右移j++;} else {// 总和大于 0，说明需要减小和，将右指针左移k--;}}}return result;}public static void main(String[] args) {int[] nums = {-1, 0, 1, 2, -1, -4};List<List<Integer>> result = threeSum(nums);for (List<Integer> triplet : result) {System.out.println(triplet);}}
}

代码解释

1、输入检查：首先检查数组是否为空或者长度是否小于 3，如果是则直接返回空列表。

2、数组排序：使用 Arrays.sort(nums) 对数组进行排序，为后续的双指针操作和去重做准备。

3、遍历第一个数：使用 for 循环遍历数组，固定第一个数 nums[i]。如果 nums[i] 大于 0，由于数组已排序，后面的数都大于 0，不可能找到和为 0 的三元组，直接跳出循环。同时，跳过重复的第一个数。

4、双指针查找：初始化双指针 j 和 k，分别指向 i 的下一个元素和数组末尾。计算三个数的和 total，根据 total 的值进行不同的操作：