给定一个数X，在两个已排序数组A和B中找到两个元素，使得它们的和等于X，并且时间复杂度为O(n+m)。

Question

给定以下问题，如有纰漏请指正，因为我没有当前问题的解决方案（取自我的教授的考试!!!）:

注意：这不是作业！

问题：

给定两个已排序数组A（长度为n）和B（长度为m），其中每个元素（在两个数组中）都是实数，以及一个数字X（也是实数），我们想知道是否存在a∈A和b∈B，使得：

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

解决方案：

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

i = n k = m while A[i] > X，i = i - 1 while B[k] > X，k = k - 1

定义j = 0。 现在从A中的当前i和B中的j开始运行：

while i > 0，j < k： if A[i]+B[j] == X，则返回两个单元格 else j = j+1，i = i -1

最后，我们将拥有两个元素，或者我们将达到一个或两个数组的边界，这意味着确实不存在两个元素，例如a+b=X.

非常感谢您的任何评论。

- JAN

---

也许你可以用伪代码写下整个算法。英语和伪代码混合在一起会让我感到困惑。 - Marijn van Vliet

注意，您可以省略预处理。 您可以将递减i留给主循环，对于j使用适当的循环条件（j ≤ m和B [j] ≤ X）。 在允许数组中有负数的情况下，不应进行任何这样的优化。 - MvG

Answer 1

你不应该同时调整变量i和j。如果它们的和太大，你应该减小i；如果它们的和太小，你应该增加j。

- MvG

---

很棒的发现。但是，这是否仍然导致O(n*m)的解决方案呢？ - BlackVegetable

@BlackVegetable：时间复杂度为O(n+m)，是的，没错。在每一步中，您要么在一个数组中移动，要么在另一个数组中移动，因此结合起来，您不能移动比两个数组长度之和更多的次数。 - MvG

Answer 2

这个问题是以下问题的特殊情况： 在O(log n)时间内在排序矩阵(行n列)中查找数字 考虑一个由填充的矩阵，然后从其中一个角开始，如果和太大，则减小，如果和太小，则增加。 当然，您不必在程序中创建和/或填充此矩阵，只需假设您知道这个矩阵的任何元素：，您随时可以立即计算它。得到的算法是。

- unkulunkulu

---

我放了一个更简洁的问题链接 :) - unkulunkulu

Answer 3

我有一个与作业相关的问题。 在查询互联网之前我已经自己努力尝试解决了。 这是我的解决方案（使用Python编写），希望一些大佬看到后能够提供改进意见。

# 1.3. Given two sorted arrays a and b and number S. Find two elements such that sum a[i] + b[j] = S.Time O(n).

def find_elem_sum(列表A, 列表B, 目标和): # O(n)

if alist is None or alist == [] or blist is None or blist == []:
    return None

# find the numbers which are less than S in the lists
#
#
# pretend it is done

a_length = len(alist)
b_length = len(blist)
a_index, b_index = 0, 0
count = 0
while alist and a_index < a_length and b_index < b_length:
    count += 1
    if alist[a_index] + blist[b_index] < S:
        if a_index < a_length - 1:
            a_index += 1
        if a_index == a_length - 1:
            b_index += 1;
        continue
    elif alist[a_index] + blist[b_index] > S:
        alist = alist[:a_index]
        a_length = len(alist)
        a_index = a_length - 1
    elif alist[a_index] + blist[b_index] == S:
        return [a_index, b_index, count]

return None

- Guan