papamelon 200. 抽签 II

地址 https://www.papamelon.com/problem/200

解答
比起抽签I 范围扩大了，那么O(n^3)的复杂度的算法已经不适合了。
我们记录任意两个签上的数字的和并记录下来，时间复杂度是O(n^2)。
然后遍历任意两个签的数字相加后还需要加多少数字才能得到指定的和。然后在记录中二分寻找
那么时间复杂度就是O(n^2log(n2)) 可以接受.

#include <iostream>
#include <algorithm>
#include <memory.h>
#include <algorithm>

using namespace std;

const int N = 1010;
int arr[N];
int partSum[N*N]; int sumIdx;

int n, m;


int bsearch(int f) {
	int l = 0; int r = sumIdx - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (partSum[mid] >= f) { r = mid; }
		else { l = mid + 1; }
	}

	if (partSum[l] == f)
		return 1;

	return 0;
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) { cin >> arr[i]; }

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			partSum[sumIdx] = arr[i] + arr[j]; sumIdx++;
		}
	}

	sort(partSum, partSum + sumIdx);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int find = m - arr[i] - arr[j];
			if (bsearch(find) == 1) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	cout << "No" << endl;
	return 0;
}

也可以不使用二分算法而是用哈希算法，方法类似
我们记录任意两个签上的数字的和并记录进哈希表，时间复杂度是O(n^2)。
然后遍历任意两个签的数字相加后还需要加多少数字才能得到指定的和。然后在哈希记录中哈希寻找

#include <iostream>
#include <unordered_set>

using namespace std;

const int N = 1010;
int arr[N];
int n,m;
unordered_set<int> ss;


int main(){
	cin >> n >>m;
	for(int i = 0;i <n;i++){cin>>arr[i];}

	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++){
		
				int find = m - arr[i]-arr[j];
				if(ss.count(find)!=0) {
					cout <<"Yes"<<endl;
					return 0;
				}
				ss.insert(arr[i]+arr[j]);
	
		}
	}
	cout <<"No"<<endl;
	return 0;
	
}

我的视频题解空间