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

题目内容

三元组：在整数数组 $nums$ 中，选取三个下标 $i$、$j$、$k$，若它们满足 $i \neq j$、$i \neq k$ 且 $j \neq k$，则将 $[nums[i], nums[j], nums[k]]$ 称为一个三元组。

重复三元组：如果两个三元组包含的三个整数完全相同，仅元素排列顺序可能不同，则它们被视为重复三元组。

给定整数数组 $nums$，请找出所有满足 $nums[i] + nums[j] + nums[k] = 0$ 的三元组，并输出这些三元组。答案中不能包含重复三元组。输出顺序以及每个三元组内部元素的顺序均不影响答案正确性。

约束条件：

• 数组长度 $n$ 满足 $3 \le n \le 3000$。
• 数组元素 $nums[i]$ 满足 $-10^5 \le nums[i] \le 10^5$。

输入描述

输入共两行。

• 第一行包含一个整数 $n$，表示数组 $nums$ 的长度。
• 第二行包含 $n$ 个整数 $nums_0, nums_1, \ldots, nums_{n-1}$，数字之间以空格分隔。

输出描述

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

样例1

输入

6
-2 0 1 1 2 -1

输出

-2 0 2
-2 1 1
-1 0 1

说明

数组长度为 6，数组中的数分别是 -2、0、1、1、2、-1。

选取下标 0、1、4，对应数分别是 -2、0、2，满足 $-2+0+2=0$，因此得到三元组 -2 0 2。

选取下标 0、2、3，对应数分别是 -2、1、1，满足 $-2+1+1=0$，因此得到三元组 -2 1 1。数组中虽然有两个 1，但该三元组只计一次。

选取下标 1、2、5，对应数分别是 0、1、-1，满足 $0+1+(-1)=0$，因此得到三元组 -1 0 1。

没有其他不同的三元组。

样例2

输入

3
0 0 0

输出

0 0 0

说明

数组长度为 3，三个数都是 0。

选取下标 0、1、2，对应数分别为 0、0、0，满足 $0+0+0=0$。

三个整数完全相同，因此该三元组只输出一次。

样例3

输入

5
-100000 0 100000 1 -1

输出

-100000 0 100000
-1 0 1

说明

数组长度为 5，数组中的数分别是 -100000、0、100000、1、-1。

选取下标 0、1、2，对应数分别是 -100000、0、100000，满足 $-100000+0+100000=0$，因此得到三元组 -100000 0 100000。

选取下标 1、3、4，对应数分别是 0、1、-1，满足 $0+1+(-1)=0$，因此得到三元组 -1 0 1。

没有其他不同的三元组。