← 返回题目列表

Codeforces · 1698/C

C. 3SUM 关闭

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$。如果对于所有不同的索引 $$$i$$$、$$$j$$$、$$$k$$$,总和 $$$a_i + a_j + a_k$$$ 是数组的一个元素,则该数组称为 3SUM 闭合数组。更正式地说,如果对于所有整数 $$$1 \leq i < j < k \leq n$$$,存在某个整数 $$$1 \leq l \leq n$$$ 使得 $$$a_i + a_j + a_k = a_l$$$,则 $$$a$$$ 是 3SUM 闭集。

确定 $$$a$$$ 是否是 3SUM 闭的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — 数组的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果 $$$a$$$ 是 3SUM 闭合的,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

示例

输入 #1

4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

输出 #1

YES
NO
YES
NO

注意

在第一个测试用例中,只有一个三元组,其中 $$$i=1$$$、$$$j=2$$$、$$$k=3$$$。在本例中,$$$a_1 + a_2 + a_3 = 0$$$,它是数组的一个元素 ($$$a_2 = 0$$$),因此该数组是 3SUM 闭的。

在第二个测试用例中,$$$a_1 + a_4 + a_5 = -1$$$,它不是数组的元素。因此,该数组不是 3SUM 闭数组。

在第三个测试用例中,对于所有不同的 $$$i$$$、$$$j$$$、$$$k$$$ 和 $$$0$$$ 来说,$$$a_i + a_j + a_k = 0$$$ 是数组的一个元素,因此该数组是 3SUM 闭合的。