题目描述

给定两个升序排序的有序数组A和B，以及一个目标值x，请你求出满足A[i] + B[j] = x的数对(i, j)。

数据保证有唯一解。

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

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

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

输出格式
共一行，包含两个整数 i 和 j。

数据范围
数组长度不超过1000000。
同一数组内元素各不相同。
1≤数组元素≤109

样例

输入样例：

4 5 6
1 2 4 7
3 4 6 8

输出样例：

1 1

算法1

(暴力枚举) $O(n^2)$

暴力就不说了 两重循环
leetcode的第一题 也是简单 和这里的简单 意义完全不一样。
差别大概就是学生面试和竟赛圈的区别吧

但是我们可以一遍哈希法
输入A组的时候 哈希表记录数值和数值所在数组的索引
在输入B数组的时候 输入一个值 直接计算需要查找的值 也就是 X-input
如果存在这里值 打印这个值在A数组的索引 + 空格 + 当前数字的索引

C++ 代码

#include <unordered_map>
#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n,m,x;
unordered_map<int,int> ma;
unordered_map<int,int> mb;

int main()
{
    scanf("%d %d %d",&n,&m,&x);
    int t;
    for(int i = 0;i <n;i++){
        scanf("%d",&t);
        ma[t] = i;
    }

    for(int i = 0;i <m;i++){
        scanf("%d",&t);
        int find = x-t;
        if(ma.count(find) != 0){
             cout << ma[find] << " " << i << endl;
        }
    }



    return 0;
}