算法1
(二分) $O(nlogm)$
数组有序,考虑二分
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main() {
int n, m, x;
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 < n; i++) {
int l = 0, r = m - 1;
while (l < r) {
int mid = l + r >> 1;
if (b[mid] >= x - a[i]) r = mid;
else l = mid + 1;
}
if (b[l] + a[i] == x) {
printf("%d %d\n", i, l);
break;
}
}
return 0;
}
算法2
(双指针) $O(n)$
i:0 -> n枚举,j:m-1 -> 0枚举。
因为是升序排列,当i增大,只有j减小它们的和才有可能减小或保持不变,否则它们的和会变得比之前大。
C++ 代码
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int main() {
int n, m, x;
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, j = m - 1; i < n; i++) {
while (j >= 0 && a[i] + b[j] > x) j--;
if (a[i] + b[j] == x) {
printf("%d %d\n", i, j);
break;
}
}
return 0;
}