数组元素的目标和 (继续探讨双指针)

举报
irrational 发表于 2022/01/17 23:11:53 2022/01/17
【摘要】 给定两个升序排序的有序数组 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。