一.题目描述
给你一个整数数组 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-105 <= nums[i] <= 105
四.解法:
方法一：排序 + 双指针
我们注意到，题目不要求我们按照顺序返回三元组，因此我们不妨先对数组进行排序，这样就可以方便地跳过重复的元素。
接下来，我们枚举三元组的第一个元素 nums[i]，其中 0≤i<n−2。对于每个 i，我们可以通过维护两个指针 j=i+1 和 k=n−1，从而找到满足 nums[i]+nums[j]+nums[k]=0 的 j 和 k。在枚举的过程中，我们需要跳过重复的元素，以避免出现重复的三元组。
具体判断逻辑如下：
如果 i>0 并且 nums[i]=nums[i−1]，则说明当前枚举的元素与上一个元素相同，我们可以直接跳过，因为不会产生新的结果。
如果 nums[i]>0，则说明当前枚举的元素大于 0，则三数之和必然无法等于 0，结束枚举。
否则，我们令左指针 j=i+1，右指针 k=n−1，当 j<k 时，执行循环，计算三数之和 x=nums[i]+nums[j]+nums[k]，并与 0 比较：
- 如果 x<0，则说明 nums[j] 太小，我们需要将 j 右移一位。
- 如果 x>0，则说明 nums[k] 太大，我们需要将 k 左移一位。
- 否则，说明我们找到了一个合法的三元组，将其加入答案，并将 j 右移一位，将 k 左移一位，同时跳过所有重复的元素，继续寻找下一个合法的三元组。
枚举结束后，我们即可得到三元组的答案。
时间复杂度 O(n2)，空间复杂度 O(logn)。其中 n 为数组的长度。
五.代码
Java代码
class Solution {public List<List<Integer>> threeSum(int[] nums) {// 首先对数组进行排序Arrays.sort(nums);// 用于存储结果的列表List<List<Integer>> ans = new ArrayList<>();// 获取数组的长度int n = nums.length;// 遍历数组，寻找三元组for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {// 跳过重复的元素，避免重复的三元组if (i > 0 && nums[i] == nums[i - 1]) {continue;}// 使用双指针法int j = i + 1, k = n - 1;while (j < k) {// 计算当前三元组的和int x = nums[i] + nums[j] + nums[k];// 根据和的大小调整指针if (x < 0) {++j; // 如果和小于0，移动左指针以增加和} else if (x > 0) {--k; // 如果和大于0，移动右指针以减小和} else {// 如果和为0，找到一个三元组ans.add(List.of(nums[i], nums[j++], nums[k--]));// 跳过重复的元素while (j < k && nums[j] == nums[j - 1]) {++j;}while (j < k && nums[k] == nums[k + 1]) {--k;}}}}// 返回结果列表return ans;}
}注释说明·排序：首先对数组进行排序，以便使用双指针法。·结果列表：ans 用于存储所有满足条件的三元组。·遍历数组：外层循环遍历数组，寻找可能的三元组。·跳过重复元素：如果当前元素与前一个元素相同，跳过以避免重复的三元组。·双指针法：使用两个指针 j 和 k，分别从当前元素的下一个位置和数组末尾开始。·计算和：计算当前三元组的和 x。·调整指针：根据 x 的值调整指针位置。·如果 x < 0，移动左指针 j。·如果 x > 0，移动右指针 k。·如果 x == 0，找到一个三元组，添加到结果列表中，并跳过重复元素。·返回结果：返回包含所有满足条件的三元组的列表。
