三数之和

题解思路

本题的目标是找到所有 和为 0 的 不重复三元组，并输出它们。

最直观的方法是 三重循环暴力枚举，但这样时间复杂度为 O(n³)，当 n = 3000 时会超时。

优化思路（双指针 + 排序）

1. 先对数组进行排序：这样可以更方便地去重，并利用双指针减少时间复杂度。
2. 固定一个数 nums[i]，然后在 i 右侧寻找两数之和等于 -nums[i]：

Leetcode 6.三数之和-原题链接

题目内容

给你一个整数数组$nums$ ，判断是否存在三元组 $[nums[i], nums[j], nums[k]]$ 满足 $i != j$、$i != k$ 且 $j != k$ ，同时还满足 $nums[i] + nums[j] + nums[k] == 0$ 。请你输出所有和为 $0$ 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

输入描述

输入共两行。

• 第一行为一个整数$n$，代表数组$nums$的长度。

• 第二行为$n$个整数$nums_0,nums_1,...,nums_{n-1}$，数字之间以空格分隔。

输出描述

输出所有满足条件的三元组。 每行代表一个三元组。三元组的数字之间以空格分隔。

样例1

输入

6 
-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

输入

3
0 1 1

输出

说明

唯一可能的三元组和不为 $0$。

样例3

输入

3
0 0 0

输出

0 0 0

说明

唯一可能的三元组和为 $0$。

提示

• $3 <= nums.length <= 3000$
• $-10^5 <= nums[i] <= 10^5$