双指针算法：数组元素的目标和

116 阅读 0 评论 77 点赞

我是靠谱客的博主沉静百褶裙，这篇文章主要介绍双指针算法：数组元素的目标和，现在分享给大家，希望可以做个参考。

题目链接：https://www.acwing.com/problem/content/802/
题意：给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。
请你求出满足A[i] + B[j] = x的数对(i, j)。
数据保证有唯一解。
数据范围
数组长度不超过1e5。
同一数组内元素各不相同。
1≤数组元素≤1e9
输入样例：
4 5 6
1 2 4 7
3 4 6 8 9
输出样例：
1 1
思路：两个单调数组，显然就可以用双指针来优化一下啦。
代码实现：

复制代码

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
27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N = 1e5+5;
int n, m, x;
int a[N], b[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m >> x;
    for(int i = 0; i < n; i ++ )
        cin >> a[i];
    for(int j = 0; j < m; j ++ )
        cin >> b[j];
    for(int i = 0, j = m - 1; i < n; i ++ ){
        while(j >= 0 && a[i] + b[j] > x) j -- ;
        if(a[i] + b[j] == x){
            cout << i << " " << j << endl;
            break;
        }
    }
    return 0;
}