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

Question

鉴于以下问题,我很感激任何更正,因为我对当前的问题没有解决方案(取自我教授的一个考试!!!):

备注:这不是功课!

问题:

给定两个排序的数组A(具有长度n)和B(具有长度m),每个数组

element(在两个数组中)是一个实数和一个数字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.现在开始从当前的iin A和jin中开始运行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.