AcWing 800. 数组元素的目标和——算法基础课题解
原文中文，约3000字，阅读约需7分钟。
📝
内容提要
给定两个升序排序的有序数组A和B，以及一个指针值x。求满足A[i]+B[j]=x的数对(i,j)。数组长度不超过10^5。
🔎
延伸解读
双指针解法的效率优势
文章给出的C++代码采用双指针法，利用数组升序特性，从A的头部和B的尾部开始遍历，时间复杂度为O(n+m)。相比暴力枚举所有数对，这种方法能高效处理长度10^5的数据，避免超时。
哈希表解法的替代思路
文章还提供了Go语言的哈希表解法，将数组A的元素和下标存入map，然后遍历B查找目标差值。这种方法时间复杂度为O(n+m)，但需要额外空间，适合对空间要求不高的场景。
数据范围与边界处理
数组元素最大可达10^9，两数之和可能超出32位整数范围，因此代码中使用long long或int64存储x和数组元素。同时，题目保证唯一解，简化了输出逻辑。
❓
Q&A
如何找到满足 A[i] + B[j] = x 的数对？
可以通过双指针法，从数组 A 的开始和数组 B 的末尾同时遍历，调整指针以找到满足条件的数对。
输入格式是什么样的？
输入格式包括三行，第一行是三个整数 n, m, x，第二行是数组 A 的 n 个元素，第三行是数组 B 的 m 个元素。
输出结果的格式是什么？
输出格式为一行，包含两个整数 i 和 j，表示满足条件的数对的下标。
数组的长度限制是什么？
数组长度不超过 10^5，且同一数组内元素各不相同。
如何确保输入数据有唯一解？
题目保证输入数据的条件下，存在唯一解，因此可以通过算法直接找到满足条件的数对。
示例输入和输出是什么？
示例输入为：4 5 6，1 2 4 7，3 4 6 8 9，输出为：1 1。
🏷️
