题意: 给定长度为$n$的序列$a$,长度为$m$的序列$b$,以及一个目标和$target$,求出$a$序列和$b$序列中所有和为$target$的数对。
数据范围:$1\leq n, m\leq 10^5, 1\leq a_i, b_i, target\leq 10^9$
题解:
本题解法为双指针,下面主要说明为什么双指针是正确的。
sum为每个状态下$a[i]$和$b[j]$之和。
-
初始情况下:$i=1,j=m$
-
如果$a[i]+b[j]=target$,则该答案$ok$
-
如果$a[i]+b[j]>target$,则左移$j$,此时选择右移$i$则$sum$变大,左移$j$可以使得$target$变小。
-
如果$a[i]+b[j]<target$,则右移$i$,此时如果选择左移$j$则$sum$变小,右移$i$可以使得$target$变大。
本题并不能使得两个数组中出现相同元素,试想下如果$a$中元素都相同,$b$中元素都相同,且$a[i]+b[j]=target$,此时有$n\times m$种答案,$O(nm)$的时间复杂度并不能通过本题。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for(int i = 1; i <= m; ++i) scanf("%d", &b[i]);
for(int i = 1, j = m; i <= n; ++i) {
while(j >= 1 && a[i] + b[j] > k) --j;
if(j >= 1 && a[i] + b[j] == k) printf("%d %d\n", i - 1, j - 1);
}
return 0;
}