Codeforces Round 803 (Div. 2) C. 3SUM Closure （数学模拟 + 暴力枚举）

给你一个长度为 n 的数组 a 。如果对于所有不同的索引 i ， j ， k ，和 ai+aj+ak 都是数组的元素，那么这个数组称为 3SUM 闭合数组。更正式地说，如果对于所有整数 1≤i<j<k≤n 存在某个整数 1≤l≤n 使得 ai+aj+ak=al 是 3SUM 闭合的，那么 a 就是 3SUM 闭合的。

判断 a 是否 3SUM 闭合。

输入
第一行包含一个整数 t ( 1≤t≤1000 ) - 测试用例数。

每个测试用例的第一行包含一个整数 n ( 3≤n≤2⋅105 ) - 数组的长度。

每个测试用例的第二行包含 n 个整数 a1,a2,…,an ( −109≤ai≤109 ) - 数组的元素。

保证所有测试用例中 n 的总和不超过 2⋅105 。

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

您可以在任何情况下输出 "YES "和 “NO”(例如，字符串 “yEs”、"yes "和 "Yes "将被视为肯定回答)。

值得学习的一道题目，这是一道需要不同以往的思考方式的题目。

如果你顺着思路走，想要找到某种优化存储数组或者更快捷的遍历数组的方式，那就正中这道题下怀了，你会发现没有任何想法。

这时候我们来思考数组能有什么元素组成。

数组可以有正数，负数和0组成。
在正数大于等于3个的时候，我们想到一定可以取出数组中最大的三个数，这三个数组合而成的数一定是大于数组中任何数的，换言之也就没有在数组中相同的数。
同理也可以得到负数大于等于3个的时候也是无解。

那么0的情况呢。
如果我们有大于等于3个的0，是否有任何意义？
答案是没有，任取三个0组合都会是0，那么一定是存在的，并且只会出现2个0和一个其他数或者1个0和两个其他数组合，那么2个0就足以满足所有情况。

所以我们删去大于2个的0。

那么现在剩下的元素不会超过6个，那么就可以直接进行三重暴力枚举即可。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
//#define int long long
#define endl '\n'

int a[N];

void solve(){
    int n;cin >> n;
    int flagMinus = 0;
    int flagPosi = 0;
    int cnt0 = 0;
    map<int,bool>st;
    map<int,bool>isNums;

    for(int i = 1;i <= n;i++){
        cin >> a[i];
        isNums[a[i]] = 1;
        if(a[i] < 0)flagMinus ++;
        if(a[i] > 0)flagPosi ++;
        if(a[i] == 0 && cnt0 <= 2)cnt0++;
        else if(a[i] == 0)st[i] = 1;
    }

    if(flagMinus > 2){
        cout << "NO\n";
        return;
    }

    if(flagPosi > 2){
        cout << "NO\n";
        return;
    }

    vector<int>nums;
    for(int i = 1;i <= n;i++){
        if(!st[i]){
            for(int j = 1;j <= n;j++){
                if(!st[j] && i != j){
                    for(int k = 1;k <= n;k++){
                        if(!st[k] && j != k && i != k){
                            nums.push_back(a[i] + a[j] + a[k]);        
                        }
                    }
                }
            }
        }
    }

    for(int i : nums){
        if(!isNums[i]){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

int main(){
    int T;cin >> T;
    while(T--){
        solve();
    }
    return 0;
}