AcWing 800. 数组元素的目标和
原题链接
简单
作者:
世事无常
,
2024-11-01 16:58:13
,
所有人可见
,
阅读 2
首先读入数据,然后思考朴素写法
`{
for( i=0;i<n;i++)
for( j=0;j<m;j++)
if(A[i]+B[i]==x) cout<<i<<" "<<j;break;
}`
观察A[i],B[j]组成x的方式,可以发现x与其成正相关,故求的结果大于x时应减小A[i]或B[j]以接近x。
小于时同理。
这里选择B[j]作为减变量;从m-1开始遍历,A[i]从0开始遍历。当A[i]+B[j]小于x时,右移指针i,反之左移指针j。最坏情况下A[n-1]+B[0]=x,时间复杂度O(2n)。以下是代码示例:
`#include<iostream>
using namespace std;
#define N 100010
int A[N],B[N];
int main()
{
int n,m,x;
cin>>n>>m>>x;
for(int i=0;i<n;i++)
{
cin>>A[i];
}
for(int i=0;i<m;i++)
{
cin>>B[i];
}
int i=0,j=m-1;//定义指针
while(A[i]+B[j]!=x)
{
if(A[i]+B[j]<x) i++;
else j--;
}
cout<<i<<" "<<j;
}`