You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

2.2 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 800. 数组元素的目标和

一、题目描述

给定两个升序排序的有序数组 AB,以及一个目标值 x

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)

数据保证有唯一解。

输入格式 第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x

第二行包含 n 个整数,表示数组 A

第三行包含 m 个整数,表示数组 B

输出格式 共一行,包含两个整数 ¥ij

数据范围 数组长度不超过 10^5。 同一数组内元素各不相同。 1≤数组元素≤10^9

输入样例:

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

输出样例:

1 1

二、思路总结

如果按传统思路,两个数组都从左到右遍历,时间复杂度妥妥的O(M*N),性能太差!

  • 发现如果A[i]+B[j]要是大于目标值x后,继续向前长大i,j都是无意义的,可以优化。

  • 如果固定i,遍历j再加上步骤1的优化是不是就可以了呢

  • 其实也缺失了一些东西:比如a[1]+b[1]<x,a[1]+b[2]<x,a[1]+b[3]<x,这样一把长大一个,长的太慢了,性能也不高。

  • 如果能一次走两个,是不是会快?那怎么能一次走两个呢?可以考虑一个从左侧出发,另一个从右侧出发。双指针,两边出发

总结

  • 双指针

  • 有序升序数组

  • 对向而行,和大了就j--,和小了就i++

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N], b[N];

int main() {
    int n, m, x;
    cin >> n >> m >> x;
    //读入a,b两个数组注意它们两个都是升序的
    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 < n; i++) {
        while (j > 0 && a[i] + b[j] > x) j--;
        if (a[i] + b[j] == x) cout << i << " " << j << endl;
    }
    return 0;
}