AcWing 800. 数组元素的目标和(map解法)
原题链接
简单
作者:
Althemeta
,
2022-02-04 18:09:43
,
所有人可见
,
阅读 353
分析:
用一个map来存储b数组中每个元素的值和下标。遍历a数组,如果x - a[i]的值(需要与a[i]配对的值)在b数组中存在,就输出a[i]的下标和它在b数组中的下标。时间复杂度: O(n + m)
Code:
#include <stdio.h>
#include <map>
#pragma GCC optimize (2)
using namespace std;
typedef pair <int, int> PII;
const int N = 1e5 + 10;
int n, m, x, a[N], b[N];
map <int, PII> h;
int main()
{
scanf ("%d %d %d", &n, &m, &x);
for (int i = 0; i < n; ++i) scanf ("%d", &a[i]);
for (int i = 0; i < m; ++i) scanf ("%d", &b[i]);
for (int i = 0; i < m; ++i) h[b[i]] = PII {b[i], i};
for (int i = 0; i < n; ++i)
{
auto it = h.find (x - a[i]);
if (it != h.end()) printf ("%d %d\n", i, it -> second.second), exit (0);
}
return 0;
}