和纯暴力的O(n^2^)算法的区别就在于

#### j指针不会回退

醍醐灌顶

真的是啊！

谢谢你科比

确实

谢谢你劳达

谢谢牢大

谢谢劳达

谢谢闹大

man!hahaha

谢谢牢大

二分

#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; 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) r = mid;
            else l = mid + 1;
        }
        if (b[l] == y)
        {
            printf("%d %d", i, l);
            break;
        }
    }

    return 0;
}

强，谢谢佬

想问一下 为什么最后不能是b[r]==y啊

l和r都可以，是一样的。最后区间里只剩一个数，l和r都指向这个数

想不到在题解代码里能看到金牌学长hh
%%%

相同的思路

#include <iostream>
using namespace std;

const int N = 1e5+10;
int q1[N],q2[N];
int main()
{
    int n1,n2,x;
    scanf("%d%d%d",&n1,&n2,&x);
    for(int i=0;i<n1;i++) scanf("%d",&q1[i]);
    for(int i=0;i<n2;i++) scanf("%d",&q2[i]);

    int l=0,r=n1-1;
    while(r>=0&&l<n2)
    {
        if(q1[r] + q2[l] > x) r--;
        else if(q1[r] + q2[l] < x) l++;
        else break;
    }
    cout<<r<<" "<<l<<endl;
    return 0;
}
//10min

哈希

#include <iostream>
#include <unordered_map>

using namespace std;

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

int main(){
    cin >>n>>m>>x;
    unordered_map<int,int> mm;
    for(int i= 0;i < n;i++) {cin >>a[i]; mm[a[i]]=i;}
    for(int j = 0; j < m;j++)cin>>b[j];

    for(int i = 0;i<m;i++){
        int find = x-b[i];
        if(mm.count(find)!=0){ cout << mm[find] <<" " << i <<endl; return 0; }
    }

    return 0;   
}

其实在输入b[i]的时候就可以判断了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int n, m;
int a[N], b[N];
unordered_map<int, int> has;
int x;

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

求问：为什么不能双指针从同一边开始啊
for(int i = 0,j = 0;i < n;i )
{
while(j < m && A[i] + B[j] < x)
{
j ;
}
if(j < m && A[i] + B[j] == x) cout<<i<<” “<<j<<endl;
}

可以想想i前进控制增j回退控制减，如果两个都前进都是控制增了

这里的双指针就是递增遍历a[i]，然后a[i]递增过头了就用j回退把sum重新减小

同时双指针同一边开始会出现漏解的情况

真妙啊

👍

这题可以用数学的方法联立两条直线，时间复杂度就是O(1)

有没有大佬解答下，为什么最后的if判断里面要加j>=0哇？while循环的条件不是已经保证了吗？

妙

有个问题，貌似有点错误，就是取j的时候，算出了大于j的最大整数，可能b[j-2],b[j-1],b[j]这三个的数值相等，但是按照题意只输出了一个j，但是测试点好像没给出来

题目要求唯一解

妙啊 不是等于就是小于

感觉加个break更顺眼

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) printf("%d %d",i,j);
    }

请问为什么A[i] + B[j] != x就会没有输出，>x就是对的呢
在顺序排列下不应该是等价的吗

<x 也是不等于啊

不不不 不等于的意思是只要不等于就会一直j–

厉害

顶顶大佬！
话说还能再抠点 A[i+1]必比A[i]大 要实现A+B = x 必然有 j ‘ <= j
所以i向下走一位，j从当前位置出发就行了(
int ans = m - 1;
for (int i = 0, j = ans; i < n; i++)
{
while (j >= 0 && A[i] + B[j] > x) ans = –j;
if (A[i] + B[j] == x)cout << i <<’ ‘<< j;
}
改成这样也能做（

read(x)我太喜欢了

#可是cin更简单hhh

纯c是信仰

我j从头开始为什么不能过？边界都是一样的 输出为空

        for (int i = 0, j = 0; i < n; i++) {
            while (a[i] + b[j] < x && j < m) {
                j++;
            }
            if (a[i] + b[j] == x) {
                System.out.println(i + " " + j);
                break;
            }
        }

因为j指针会一直往后走，按照你的代码，把样例走一下，
1 2 4 7
3 4 6 8 9
你会发现当j指到6时，i才会指到2，然后i不管是什么和j指的6相加都会大于6，所以不会输出

恍然大悟

补充一点：除了j指针不会回退 判断重复元素的方法也是很大的一个优化