algorithm - O(n) 查找 2 个数组是否有 2 个元素加起来等于一个数的算法

Question

我正在备考，遇到了这个看起来有点棘手的问题。

令 A[1...n] 和 B[1...n] 为 2 个整数数组，使得 A 或 B 的每个元素都在 0 到 m 的范围内，其中 m = O(n)。 (我假设这意味着 m < n ？)

我们需要设计一个 O(n) 算法来找到两个元素 A[i] 和 B[j] 使得 A[i]+B[j] = 给定数 k 。如果它们不存在，我们会抛出一条错误消息。

现在对它们进行排序是不可能的，因为最好的排序算法是 O(n lg n) 。

也许使用哈希表 .. 或者只是创建一个长度为 m 的较小数组 X，这样每个索引都会计算 A 中数字的出现次数 .. 然后我们遍历 B .. 计算 diff = k - B[j] .. 并检查 X[diff] .. 如果它大于零，那么是的，它存在，然后我们可以再次通过 A 找到它的索引..

大家怎么看

Answer 1

m = O(n)表示 m以 n 的常数倍数为界，不一定比它小。

你能做的就是这个。获取大小为 k+1 的数组(所以内存 O(m) 也是 O(n) )。调用此数组 C .将所有值初始化为未标记，比方说 -1。这是 O(m)这也是 O(n) .

现在你知道了 k <= 2m因为A[i]和 B[i]都是<= m .所以你遍历数组 A , 标记在 C所有k-A[i] , 所以 C[k-A[i]] = i (也就是说，如果 k-A[i] >= 0 假设索引从 0 开始)。这是 O(n) .然后遍历数组 B并且对于每个 B[j]检查是否C[B[j]]已经被标记了。如果是这样，那么 C[B[j]]在A中标记某个索引其中 B[j]+A[C[B[j]]] = k .翻过去B检查标记也是 O(n) .如果找不到匹配项，则没有这样的对。

整体算法是O(n) .

这是一个例子:

n = 5
m = 15
A = [1 7 4 2 10]
B = [8 14 3 13 11]
k = 20

过后A ，你得到:

C: [-1 -1 -1 -1 -1   -1 -1 -1 -1 -1   4 -1 -1 1 -1   -1 2 -1 3 0   -1]

(间距是为了更好的可视化)然后你检查 B :

B[0] -> C[8] -> -1 mismatch
B[1] -> C[14] -> -1 mismatch
B[2] -> C[3] -> -1 mismatch
B[3] -> C[13] -> 1 match -> B[3] + A[1] = 20

B[3]是 13 和 A[1]是 7。