本文主要是介绍【AcWing】800. 数组元素的目标和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题链接：活动 - AcWing
目录
1. 题目描述
输入格式
输出格式
数据范围
输入样例：
输出样例：
2. 思路分析
3. 代码实现
1. 题目描述
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 10^5。
同一数组内元素各不相同。
1≤数组元素≤10^9
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 12. 思路分析
双指针板题。
因为题目要求a[i]+b[j]==x，a[ ]数组和b[ ]数组均升序，且数据保证有唯一解。
暴力求解的话，复杂度为O(n*m)，为了降低复杂度，利用升序（单调）这个特性我们就可以通过双指针来优化。
我们定义 i 和 j 两个指针，i 指针用来遍历数组，让 i 最开始指向a数组开头（下标为0）的位置，让 j 最开始指向b数组末尾（也就是下标为m-1）的位置，考虑到a[i]+b[j]==x，而且两个数组均升序，当a[i]增大时，因为x为定值，所以b[j]一定减小，也就是说当 i 指针遍历数组的整个过程中， j 指针一定往左移。因为数据有唯一解，所以当 a[i]+b[j]==x时，我们输出 i 和 j，并结束程序。
3. 代码实现
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e5+10;
int a[N],b[N];signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m,x; cin>>n>>m>>x;for(int i=0;i<n;i++) cin>>a[i];for(int i=0;i<m;i++) cin>>b[i];for(int i=0,j=m-1;i>=0;i++){while(j>=0&&a[i]+b[j]>x) j--;if(a[i]+b[j]==x){cout<<i<<" "<<j<<endl; return 0;}}return 0;
}这篇关于【AcWing】800. 数组元素的目标和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
