首页 > 其他分享 >机试题 三数之和变形-三数和赛高数组02 存在

机试题 三数之和变形-三数和赛高数组02 存在

时间:2022-10-01 20:44:22浏览次数:49  
标签:02 数组 nums int 三数 sum 赛高 &&

数组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

相关文章