[Java恶补day6] 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^5$ <= nums[i] <= $10^5$

---

知识点：
数组、双指针、排序、问题转换为两数之和

---

解：
首先，我没考虑到最暴力的三个嵌套for循环，因为它的复杂度非常大，而本题的核心考点就是双指针，因此需要考虑如何将问题转换为求双指针的问题。
一个很简单的思路，就是固定其中一个数，去处理另外两个数，因此，用for循环代表第一个数的遍历。
因为题目要求结果不能包含重复的三元组，因此：
①将原始数组进行升序排序，再去遍历，得到的三元组的数字满足a≤b≤c，这样就不会出现b,a,c等顺序，因此能避免结果出现重复的三元组。
②在每次遍历中，当前处理的数字，不能和上一次遍历处理的数字相同，例如：当前第二个元素、上一次遍历的第二个元素相同，那么这样就会产生重复。因此，当遇到和上一次遍历相同的数字，就跳过当前这个数字的遍历。

基于这个分析，在对pi的for循环遍历中，定义双指针pj、pk，分别用于遍历第二个数、第三个数，并根据#两数之和这道题的思路，两个指针从两端开始向中间遍历，只要左指针指向的数字＜右指针指向的数字，就继续循环。
对于每次得到的第二个数、第三个数，我们计算三数之和sum，并有以下三种情况：
①若和为0，满足条件，就构造List，存到结果列表中。然后要更新双指针。但首先，需要判断指针遍历的元素是否与上一次遍历的元素相同，若相同，则让指针向右/左移动一格。接下来，再去同时更新双指针（这里需要同时更新双指针，是因为：小的那个数变大，为了保持和不变，大的那个数要同时变小）。
②若和＜0，表示我们要获得更大的一个数，由于第三个数代表的是三元组中最大的数，因此我们让代表第二个数的左指针右移一格。
③若和＞0，表示我们要获得更小的一个数，由于第二个数代表的是三元组中最小的数（此时我们固定了第一个数，因此可以这么描述），因此我们让代表第三个数的右指针左移一格。

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$，由于对原始数组进行了排序，因此可视为使用一个额外的数组存储了nums的副本并进行排序 【该分析源自力扣官解】

class Solution {public List<List<Integer>> threeSum(int[] nums) {//目标：数组的三个不同数字和为0//定义最终结果的数据结构List<List<Integer>> res = new ArrayList<>();//数组长度int n = nums.length;//原数组进行排序，实现最终结果的去重Arrays.sort(nums);//遍历所有元素for (int pi = 0; pi < n - 2; pi++) {//当前遍历的第一个元素需要不等于前一个元素，以降低时间复杂度if (pi > 0 && nums[pi] == nums[pi - 1]) {continue;}//问题转化为：固定第一个数的情况下，对另外两个数进行常规双指针操作//定义双指针int pj = pi + 1;int pk = n - 1;//只要左指针＜右指针，就继续循环while (pj < pk) {//计算三数之和int sum = nums[pi] + nums[pj] + nums[pk];if (sum == 0) {//满足要求，加入resList<Integer> triplets = new ArrayList<>();triplets.addAll(Arrays.asList(nums[pi], nums[pj], nums[pk]));//一次性添加三个元素res.add(triplets);//跳过重复元素while (pj < pk && nums[pj] == nums[pj + 1])pj++;while (pj < pk && nums[pk] == nums[pk - 1])pk--;//更新双指针（小的那个数变大，为了保持和不变，大的那个数要同时变小）pj++;pk--;} else if (sum < 0) {//和小于0，寻找比第二小的数稍微大一点的数pj++;} else {//和大于0，寻找比第一大的数稍微小一点的数pk--;}}}return res;}
}