二分方式
用双指针算法是O(n + m),而有序的话也很容易想到用二分来做 :)突然发现模板很有用有木有
#include <iostream>
using namespace std;
const int N = 100010;
int a[N], b[N];
int n, m, q;
int
main(void) {
int x = 0;
cin >> n >> m >> q;
for(int i = 0; i < n; i ++) cin >> a[i];
for(int i = 0; i < m; i ++) cin >> b[i];
while(x < n) {
int l = 0, r = m - 1;
while(l < r) {
int mid = l + r >> 1;
if(a[x] + b[mid] >= q) r = mid;
else l = mid + 1;
}
if(a[x] + b[l] == q) {
cout << x << ' ' << l << endl;
return 0;
}
x++;
}
}
时间复杂度
时间复杂度是O(n*lgn)