arrays - 从两个数组中查找特定的元素总和

Question

你能帮我解决这个问题吗？ :“让 A 和 B 是自然数的递增排序数组，K 是某个任意自然数。找到一个有效的算法来确定所有可能的索引对 (i,j)，使得 A[i]+B[j]=K . 证明算法的正确性并估计其复杂性。”

我是否应该只遍历第一个数组并对另一个数组进行二分查找？谢谢:)

Answer 1

不!

两个数组都是有序的，因此您执行以下操作:

• 在A的开头放置一个迭代器itA
• 在B的末尾放置一个迭代器itB
• 沿相反方向移动迭代器，在每次迭代时测试 *itA + *itB。如果该值等于 K，则返回两个索引。如果该值小于K，则递增itA。否则，递减 itB。

当你遍历两个数组时，你就在线性时间内完成了。