数组元素的目标和

题目描述
求A[i] + B[j] == k 的 (i , j) 对

样例
输入

4 5 6
1 2 4 7
3 4 6 8 9
输出

1 1
算法1
(双指针) O(n)O(n)
i从 0开始 从前往后遍历
j从 m - 1开始 从后向前遍历

和纯暴力的O(n2)O(n2) 算法的区别就在于

j指针不会回退

C++ 代码
#include
#include
using namespace std;

const int N = 1e5 + 10;

int n, m, k;
int a[N], b[N];
#define read(x) scanf(“%d”,&x)

int main()
{
read(n), read(m), read(k);
for (int i = 0; i < n; i ++ ) read(a[i]);
for (int i = 0; i < m; i ++ ) read(b[i]);

for (int i = 0, j = m - 1; i < n; i ++) {
    while(j >= 0 && a[i] + b[j] > k) j --;
    if(j >= 0 && a[i] + b[j] == k) printf("%d %d\n", i, j);
}
return 0;
1
2
3
4
5

}
首先是输入，请大家不要在意，作为一个年轻气壮的作死小伙
不作死那还是我嘛，虽然推荐大家用scanf，但此题解中我用的是cin，而且是从一读的

还望见谅
有人可能会好奇我究竟优化在哪里
给你们对比一下就知道了

y总的

我的

想必聪明的大家已经看到区别了
就是y总第一行的

j=m-1

我在程序中并未写出这一行
有人认为这根本就不是什么优化
不要小瞧他，想想我们两人的时间效率还是我略胜一筹
为什么呐？
因为y总每次的赋值语句是的下面的while循环次数变多
但有人说我做的有道理毛
就请你们看一下题目
两个序列都是单调递增序列

解析

大家一定听懂了
看下面

程序
#include
#include
#include
using namespace std;
int N[100001],m[100001];
int main()
{
int n,a,B,j=0,i=0;
cin>>n>>a>>B;
for(int i=1;i<=n;i++)cin>>N[i];
j=n;
for( i=1;i<=a;i++)//输入优化
{
cin>>m[i];
while(j>0&&N[j]+m[i]>B)j–; //while循环j第一次还是当前位置
if(N[j]+m[i]==B)
return cout< }
return 0;
}
首先是输入，请大家不要在意，作为一个年轻气壮的作死小伙
不作死那还是我嘛，虽然推荐大家用scanf，但此题解中我用的是cin，而且是从一读的

还望见谅
有人可能会好奇我究竟优化在哪里
给你们对比一下就知道了

y总的

我的

想必聪明的大家已经看到区别了
就是y总第一行的

j=m-1

我在程序中并未写出这一行
有人认为这根本就不是什么优化
不要小瞧他，想想我们两人的时间效率还是我略胜一筹
为什么呐？
因为y总每次的赋值语句是的下面的while循环次数变多
但有人说我做的有道理毛
就请你们看一下题目
两个序列都是单调递增序列

解析

大家一定听懂了
看下面

程序
#include
#include
#include
using namespace std;
int N[100001],m[100001];
int main()
{
int n,a,B,j=0,i=0;
cin>>n>>a>>B;
for(int i=1;i<=n;i++)cin>>N[i];
j=n;
for( i=1;i<=a;i++)//输入优化
{
cin>>m[i];
while(j>0&&N[j]+m[i]>B)j–; //while循环j第一次还是当前位置
if(N[j]+m[i]==B)
return cout< }
return 0;
}
首先是输入，请大家不要在意，作为一个年轻气壮的作死小伙
不作死那还是我嘛，虽然推荐大家用scanf，但此题解中我用的是cin，而且是从一读的

还望见谅
有人可能会好奇我究竟优化在哪里
给你们对比一下就知道了

y总的

我的

想必聪明的大家已经看到区别了
就是y总第一行的

j=m-1

我在程序中并未写出这一行
有人认为这根本就不是什么优化
不要小瞧他，想想我们两人的时间效率还是我略胜一筹
为什么呐？
因为y总每次的赋值语句是的下面的while循环次数变多
但有人说我做的有道理毛
就请你们看一下题目
两个序列都是单调递增序列

解析

大家一定听懂了
看下面

程序
#include
#include
#include
using namespace std;
int N[100001],m[100001];
int main()
{
int n,a,B,j=0,i=0;
cin>>n>>a>>B;
for(int i=1;i<=n;i++)cin>>N[i];
j=n;
for( i=1;i<=a;i++)//输入优化
{
cin>>m[i];
while(j>0&&N[j]+m[i]>B)j–; //while循环j第一次还是当前位置
if(N[j]+m[i]==B)
return cout< }
return 0;
}