数组a 存在 i、j、k 能找到l,使得ai + aj + ak = al,那么这个数组就是被称为三数和赛高数组,特别的i、j、k需要满足(1 <= i < j < k <= n, 1 <= l <= n)。
输入:
首先 t (1 <= t <= 1000) 代表t组数据。
然后 每组数据先输入一个n (3 <= n <= 200000), 代表数组的长度为n,接下来是n个数字a1,a2,……,an (-10^9 <= ai <= 10^9)
输出:
每组数据,如果是三数和赛高数组就输出"YES",否则输出"NO"
test1
input:
4
3
1 0 -1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4
output:
YES
YES
YES
NO
my code
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
void solution() {
int n;
cin >> n;
vector<int> nums(n);
unordered_set<int> uset;
for (int i = 0; i < n; ++i){
cin >> nums[i];
uset.insert(nums[i]);
}
sort(nums.begin(), nums.end());
// 外循环
int sum;
for (int i = 0; i < n; ++i) {
// 双指针 缩小搜索范围
if (i > 0 && nums[i] == nums[i-1]) continue;
bool flag = true;
for (int l = i + 1, r = n - 1; flag && l < r; ) {
sum = nums[i] + nums[l] + nums[r];
if (sum < nums[0]) {
while(++l < r && nums[l-1] == nums[l]) ;
}
else if (sum > nums[n - 1]) {
while(l < --r && nums[r+1] == nums[r]) ;
}
else {
for (int j = l; flag && j <= r - 1; ++j) {
for (int k = l + 1; flag && k <= r; ++k) {
sum = nums[i] + nums[j] + nums[k];
// 不符合了 退出三层for循环
if (sum < nums[0] || sum > nums[n - 1]) {
flag = false;
break;
}
else if (uset.find(sum) != uset.end()) {
cout << "YES" << endl;
return;
}
}
flag = false;
}
}
}
}
cout << "NO" << endl;
return;
}
int main() {
int t;
cin >> t;
while(t--) solution();
return 0;
}
标签:02,数组,nums,int,三数,sum,赛高,&&
From: https://www.cnblogs.com/zkx98/p/16747650.html