数组元素的目标和（双指针算法）题目描述：

104 阅读 0 评论 69 点赞

我是靠谱客的博主追寻御姐，这篇文章主要介绍数组元素的目标和（双指针算法）题目描述：，现在分享给大家，希望可以做个参考。

题目描述：

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。
数据保证有唯一解。
输入格式
第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。
第二行包含n个整数，表示数组A。
第三行包含m个整数，表示数组B。
输出格式
共一行，包含两个整数 i 和 j。

数据范围
数组长度不超过100000。
同一数组内元素各不相同。

1≤数组元素≤10⁹

输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1

解题思路：i指针枚举a数组，j指针指向b数组最后一个数，如果i+j>x的话，那i以及i后面的数+j都是不合法的，所有j-1，直到i+j<=x，那么才存在合理的可能。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
namespace IO{
    inline LL read(){
        LL o=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
        while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();}
        return o*f;
    }
}using namespace IO;
const int N=1e5+7,base=1e9;
int a[N],b[N];
int main(){
    int n,m,x;
    n=read(),m=read(),x=read();
    for(int i=0;i<n;i++)a[i]=read();
    for(int i=0;i<m;i++)b[i]=read();
    for(int i=0,j=m-1;i<n;i++){//i枚举a数据
        while(j>=0&&a[i]+b[j]>x)j--;//如果i+j>x,那么i及i后的数都不合法，j--
        if(j>=0&&a[i]+b[j]==x)printf("%d %dn",i,j);
    }
    return 0;
}