数组元素的目标和 (继续探讨双指针)
【摘要】
给定两个升序排序的有序数组 A和 B,以及一个目标值 x。
数组下标从 0开始。请你求出满足 A[i]+B[j]=x的数对 (i,j)。数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x。
第二行包含 n个整数,表示数组 A。
第三行包含 m个整数,表示数组 B...
给定两个升序排序的有序数组 A和 B,以及一个目标值 x。
数组下标从 0开始。请你求出满足 A[i]+B[j]=x的数对 (i,j)。数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x。
第二行包含 n个整数,表示数组 A。
第三行包含 m个整数,表示数组 B。
输出格式
共一行,包含两个整数 i和 j。
数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
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, j = m - 1; i < n; i ++ )
{
while (j >= 0 && a[i] + b[j] > x) j -- ;
if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;
}
return 0;
}
我们可以看到,i从左向右,j从右向左,只要满足了条件,就会break掉输出结果,这很大程度上也取决于单调性,复杂度为O(m+n)
文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/weixin_54227557/article/details/120596462
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)