历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 800. 数组元素的目标和（三种方法！超全！）原题链接简单

作者：

天元之弈 , 2022-09-20 13:50:31 , 所有人可见 , 阅读 5481

97

36

算法基础课题解合集

二分

二分思路

既然要找两个和为 $x$ 的数，那么我们可以把它转换成确定了一个 $y$ 为 $A_i$ 然后快速在 $B$ 中找出 $x - y$ 的问题。

显然我们可以二分查找，算法复杂度为 $O(nlogn)$ ，可以 $AC$ 。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int a[N], b[N];
int n, m, x;

int main() {
    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 ++) {
        int y = x - a[i];
        int l = 0, r = m - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (b[mid] == y) {
                cout << i << " " << mid << endl;
                return 0;
            } else if (b[mid] < y) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    return 0;
}

双指针

双指针思路

我们先简化一下问题，变成求 $A_i + B_j >= x$ 且 $j$ 要最小。

我们用可以一个指针 $i$ 枚举 $A$ 中的所有数，而 $j$ 则用来枚举 $B$ ，但由于数组是单调递增的，所以如果 $A_i + B_j \ge x$ 那么 $B_{j + 1}$ 到 $B_m$ 就不可能是答案。

所以 $j$ 是只能递减的，如此，我们便可以用 $O(n + m)$ 的时间复杂度通过这道题。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

int main() {
    cin >> n >> m >> x;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= m; i ++) cin >> b[i];
    for (int i = 1, j = m; i <= n; i ++) {
        while (j >= 0 && a[i] + b[j] >= x) j --;
        if (j >= 0 && b[j + 1] + a[i] == x) // 注意这里的下标，感谢大佬的指正
            cout << i - 1 << " " << j << endl;
    }
    return 0;
}

哈希

思路

我们可以在输入 $A$ 时把每个数存进哈希表里，对于每个输入的 $B_i$ 看看 $x - B_i$ 是否出现与哈希表即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];
unordered_map<int, int> h;

int main() {
    cin >> n >> m >> x;
    for (int i = 0; i < n; i ++) {
        cin >> a[i];
        h[a[i]] = i;
    }
    for (int i = 0; i < m; i ++) {
        cin >> b[i];
        if (h.count(x - b[i])) 
            cout << h[x - b[i]] << " " << i << endl; 
    }
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$

39 评论

15090520389 2024-09-19 18:27

大佬啊哈希表真的妙

Mr锤子 2023-03-20 10:40

大佬，第一个二分写法if (b[mid] == y) { cout << i << " " << mid << endl; return 0;
如果不return 0为什么会超时，怎么想到＋return 0的

天元之弈 2023-03-21 18:00

因为这题有唯一解

李元泽 2023-03-15 14:05

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

int main() {
    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 (j >= 0 && b[j + 1] + a[i] == x)        //这里必须是if (j >= -1 && b[j + 1] + a[i] == x)
            cout << i << " " << j + 1 << endl;
    }
    return 0;
}

例子:
2 3 5
1 3
2 2
可以知道3 + 2 = 5,3的位置是i = 1,5的位置是j = 0,而对应我们的程序运行对应的解为i = 1;j = -1
而我们的程序if (j >= 0 && b[j + 1] + a[i] == x)会把这种情况退出,从而导致无解,所以要改为if (j >= -1 && b[j + 1] + a[i] == x)

李元泽 2023-03-15 14:06

双指针算法

天元之弈 2023-03-17 20:59 回复了李元泽的评论

这数据是不是有问题，B的长度是2不是3

李元泽 2023-03-18 18:53 回复了天元之弈的评论

这是y总的测试数据，没有问题，

天元之弈 2023-03-18 18:59 回复了李元泽的评论

m = 3，说明B数组的长度就是3，但你B只有两个数，显然有问题啊

李元泽 2023-03-18 19:04 回复了天元之弈的评论

那里打错了，是二

李元泽 2023-03-18 19:05 回复了天元之弈的评论

你可以试试

李元泽 2023-03-18 19:06 回复了天元之弈的评论

2 2 3
1 2
1 3

天元之弈 2023-03-18 19:38 回复了李元泽的评论

已经修改了，强迫症不太喜欢-1，就把数组下标改了qwq

笨蛋小狗要加油 2023-04-06 23:55

#include <iostream>
using namespace std;
const int N=10e5+10;
int n,m,x,a[N],b[N];

int main()
{
    cin>>n>>m>>x;
    for(int i=0;i<n;i++)    scanf("%d",&a[i]);
    for(int j=0;j<m;j++)    scanf("%d",&b[j]);

    //我们先简化一下问题，变成求 Ai+Bj>=x且j要最小
     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;
             break;
       }
     }
    return 0;
}

笨蛋小狗要加油 2023-04-06 23:56 回复了笨蛋小狗要加油的评论

这样也可以，就是楼主的思路，稍微简洁一些

羡笙雨 2024-04-11 10:40

天才啊，老弟，双指针解法犀利；

南笙离梦 2023-02-24 21:18

感觉查找匹配还是哈希比较好写

acwing_16169 2025-02-27 14:29 · 湖南

#include [HTML_REMOVED]

using namespace std;

const int N = 100010;
int a[N];
int b[N];

int main(){
int n1,n2,x;
cin >> n1 >> n2 >> x;

for(int i=0; i<n1; i++) cin >> a[i];
for(int j=0; j<n2; j++) cin >> b[j];

int j = n2 - 1;
for(int i =0; i<n1; i++)
{
    while(j>0 && a[i] + b[j] > x) j--;
    if(a[i] + b[j] == x) cout << i << " " << j << endl;
}


return 0;

}

双指针不需要去特判J，不让他等于0就好了

相顾无言 2024-04-01 15:17

双指针有点不太懂为什么等于也要j–

..._210 2024-03-27 00:01

我咋就想不到呢

无限前进 2024-03-22 17:21

这个哈希，实在是太秀了

nuyoahh 2024-01-07 13:33

牛逼啊

绿色北极熊 2023-08-01 17:02

#include [HTML_REMOVED]
#include [HTML_REMOVED]
int a[100010],b[100010];
int n,m,x;
int main()
{
scanf(“%d%d%d”,&n,&m,&x);
for(int i=0;i<n;i)
scanf(“%d”,&a[i]);
int i=0;
int j=m;
for(i=0;i<m;i)
scanf(“%d”,&b[i]);
for(i=0;i<n;i++)
{
j=x-a[i];
int l=0;
int r=m-1;
while(l<=r)//大佬为什么这里的=去掉后就得不出正确结果了？有点想不明白，大佬能解释一下吗

{int mid=l+r >>1;
if(b[mid]==j)
{
    printf("%d %d",i,mid);
    return 0;
}
else if(b[mid]>j)
r=mid-1;
else
l=mid+1;}

}

return 0;
}

未央灬 2023-03-19 11:36

这道题用二分的话，每个a[i]都会在b[i]进行二分查找，最坏的时间复杂度不应该是n✖二分的复杂度nlogn吗，这样子不会超时吗

天元之弈 2023-03-19 17:52

二分的复杂度是 $O(logn)$ 哦

未央灬 2023-03-19 19:09 回复了天元之弈的评论

但是你要循环n次，每次都要二分查找，时间复杂度最坏不就变成n^2*nlogn了

天元之弈 2023-03-19 20:25 回复了未央灬的评论

对呀，所以是 $O(n \times logn)$ 啊

天元之弈 2023-03-19 20:27 回复了天元之弈的评论

我一次二分是 $nlogn$ 那么做 $n$ 次二分，就是 $nlogn$ ，可以看代码， $for$ 一共 $n$ 次，内部循环二分每次 $logn$

未央灬 2023-03-20 11:39 回复了天元之弈的评论

哦哦，我的错，你是对的OAO

Luo_Huang 2023-02-28 17:54

二分写法里的l = mid + 1 我能理解，但为什么r = mid - 1，而不是r = mid啊，我r = mid会超时是什么原因呢

天元之弈 2023-02-28 21:41

注意看我写的是 $l<=r$ ，这样子的模板虽然时间不如y总的（会多执行一次），但是固定一个模板，不容易错

Luo_Huang 2023-03-01 23:14 回复了天元之弈的评论

哇，好牛，学到了个新方法，想问一下如果我想用y总的板子为什么会错呀，这个样例无输出
1 2 6
1
3 5
标准答案
0 1

天元之弈 2023-03-02 07:15 回复了 Luo_Huang 的评论

你代码发我看看呗

冒泡了 2023-07-24 22:40 回复了天元之弈的评论

#include<iostream>
#include<cstdio>
#include<set>

using namespace std;

const int N=100010;
int a[N],b[N];

int main()
{
    int n,m,x;
    cin>>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;i<n;i++)
    {
        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[l]+a[i]==x)
        {
            cout<<l<<" "<<i<<endl;
            break;
        }
    }

    return 0;
}

这样是WA的为什么呢

天元之弈 2023-07-25 06:22 回复了冒泡了的评论

输出反了，先输出 i 再是 l，注意你上面写的是 b[l] 和 a[i]。

我是java同学 2023-02-04 20:06

哈希的时间复杂度是多少呢

我是java同学 2023-02-04 20:49

$O(1)$

天元之弈 2023-02-05 10:03

大概应该是O(N)吧

我是java同学 2023-02-05 11:11 回复了天元之弈的评论

好呢

天元之弈 2023-02-05 15:07 回复了我是java同学的评论

哈希一步是O(1)，循环n次就是O(n)

App 内打开

AcWing 800. 数组元素的目标和（三种方法！超全！） 原题链接 简单

算法基础课题解合集

二分

二分思路

既然要找两个和为 xx 的数，那么我们可以把它转换成确定了一个 yy 为 AiA_i 然后快速在 BB 中找出 x−yx - y 的问题。

显然我们可以二分查找，算法复杂度为 O(nlogn)O(nlogn)，可以ACAC。

代码

双指针