#16. 数组元素的目标和
数组元素的目标和
给定两个升序排序的有序数组 和 ,以及一个目标值 。
数组下标从 开始。
请你求出满足 的数对 。
数据保证有唯一解。
输入格式
第一行包含三个整数 ,分别表示 的长度, 的长度以及目标值 。
第二行包含 个整数,表示数组 。
第三行包含 个整数,表示数组 。
输出格式
共一行,包含两个整数 和 。
数据范围
数组长度不超过 。
同一数组内元素各不相同。
输入样例:
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 顺序”的实现问题;同时仍保证唯一解便于定位错误。