arrays - 给定一个数字 X ，在两个排序数组中找到两个元素，例如 A[i]+B[j] = X in O(n+m)

Question

鉴于以下问题，我将不胜感激，因为我没有解决方案 对于当前问题(取 self 教授的一次考试!!!):

备注:这不是作业!

问题:

给定两个排序数组 A (长度为 n )& B (长度为 m )，其中每个

元素(在两个数组中)是一个实数，一个数字 X (也是实数)，

我们想知道是否存在a ∈ A和 b ∈ B ，例如:

a + b = X , 在 O(n+m)运行时间。

解决方案:

首先，我们从两个数组的末尾开始检查，因为我们不需要大于X 的数字。 :

• 我=n

• k = m

• 当 A[i] > X , i = i -1

• 当 B[k] > X , k = k -1

定义 j = 0 。 现在从当前i开始运行在A , 来自j在B :

• while i > 0 , j < k :
• if A[i]+B[j] == X , 然后返回两个单元格
• 其他 j = j+1 , i = i -1

最后我们要么有两个元素，要么我们有一个越界 或两个数组，这意味着没有两个元素这样 a + b = X确实存在。

如有任何意见，我们将不胜感激

谢谢

Answer 1

你不应该同时调整i和j。如果总和太大，你应该减少i。如果太小，增加j。