找指定和(平方)的整数对

题目描述

给一个有 $n(n<1000000)$ 个整数的数组 $a$， 求两个数 $a_i,a_j$ 使其和为 $m$。

思路

先进行排序， 然后定义双指针 $i=0,j=n-1$， 显然 $i$ 变大时， 总和变大， 当 $j$ 变小时， 总和变小。

因此就当总和 > $m$ 时， $j--$ , 当 总和 < $m$ 时， $i++$。等于时就输出。

代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
 
const int N = 2e5 + 10;
int a[N];
int q[N], f[N];
 
void solve() {
    int n,m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	for(int i = 1, j = n; i <= j; )
	{
		int sum = a[i] + a[j];
		if(sum > m) j--;
		else if(sum < m) i++;
		else cout << a[i] << " " << a[j] << endl;
	}
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--)
    solve();
    return 0;
}