YACS（上海计算机学会竞赛平台）三星级挑战——两数之和

题目描述

给定?n?个整数 a[1]?,a[2]?,?,a[n]?，并且保证

a[1?]≤a[2?]≤?≤a[n]?

再给定一个目标值?t，请判断能否找到?a[i]??与?a[j]?，ai?+aj?=t?且 i≠j。

输入格式

第一行：单个整数n；

第二行：n个整数a[1],a[2],...,a[n]；

第三行：单个整数t。

输出格式

如果存在一种组合满足要求，输出Yes，否则输出No。

数据范围

样例数据

输入：

4

1 3 5 7

8

输出：

Yes

说明：

8=3+5

输入：?

4

2 4 6 8

11

输出：

No

输入：

3

1 2 5

2

输出：

No

说明：

1+1不是一个符合条件的解法，因为输入数据里只有一个1；
单个2也不能算一个符合条件的解法，因为不配对

主要思想

定义左指针与右指针，如果左指针+右指针=t的话，输出“Yes”，如果while循环结束还不输出“Yes”，输出“No”。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n, t;
int a[1000005];
long long ans;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);
	cin>>t;
	int l = 1, r = n; //左指针与右指针
	while (l < r) {
		if (a[l] + a[r] > t) {
			r--;
		} else if (a[l] + a[r] < t) {
			l++;
		} else {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}