AcWing 800. 数组元素的目标和
原题链接
简单
作者:
m_math
,
2024-04-08 17:12:45
,
所有人可见
,
阅读 6
双指针
#include <iostream>
using namespace std;
const int N = 100010;
int n,m,x;
int a[N],b[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> x;
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;
}
二分
#include <iostream>
using namespace std;
const int N = 100010;
int n,m,x;
int a[N],b[N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m >> x;
for(int i = 0;i < n;i++)
cin >> a[i];
for(int i = 0;i < m;i++)
cin >> b[i];
for(int i = 0;i < n;i++)
if(a[i] < x)
{
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[r] == x - a[i])
cout << i << ' ' << r << endl;
}
return 0;
}