#16. 数组元素的目标和

数组元素的目标和

给定两个升序排序的有序数组 AABB,以及一个目标值 xx

数组下标从 00 开始。

请你求出满足 A[i]+B[j]=xA[i] + B[j] = x 的数对 (i,j)(i, j)

数据保证有唯一解。

输入格式

第一行包含三个整数 n,m,xn,m,x,分别表示 AA 的长度,BB 的长度以及目标值 xx

第二行包含 nn 个整数,表示数组 AA

第三行包含 mm 个整数,表示数组 BB

输出格式

共一行,包含两个整数 iijj

数据范围

数组长度不超过 10510^5
同一数组内元素各不相同。
1数组元素1091 \le 数组元素 \le 10^9

输入样例:

4 5 6
1 2 4 7
3 4 6 8 9

输出样例:

1 1

数据 1(样例风格):基础正确性。

数据 2(解在 A[0] + B[m-1]):卡双指针初始化/移动方向写反、以及边界处理。

数据 3(解在 A[n-1] + B[0]):卡另一侧边界;也卡只从固定方向扫导致漏解。

数据 4(接近 1e9,x > 2^31):卡 32 位 int 溢出(A[i]+B[j] 需要用 64 位)。

数据 5(n=1):卡极小边界(循环条件/指针越界/输出格式)。

数据 6(m=1):同上,卡单列数组边界处理。

数据 7(需要多次移动指针才能命中):卡双指针更新逻辑(sum<x 应 i++,sum>x 应 j--),以及写反导致死循环/错过解。

数据 8(答案为 “3 0”):专门卡 把下标当 1-based 输出 的错误(会输出 4 1 之类直接 WA)。

数据 9(n=100000, m=9999 大数据):强力卡复杂度:暴力 O(n*m) 会 TLE;正确应双指针 O(n+m) 或二分 O(n log m)。

数据 10(中等规模但“唯一性构造”强):卡一些“误用哈希/二分边界错误/输出错 i j 顺序”的实现问题;同时仍保证唯一解便于定位错误。