algorithm - 找到三个索引 x、y、z，使得 M[x] + M[y] = N[z]

Question

给定两个数组(未排序)M 和 N。我必须找到三个索引 x、y(在 M 中)和 z(在 N 中)，使得 M[x] + M[y] = N[z]。 我的初始算法需要 O(m *m *n) 解决方案。请注意，我必须找到索引，排序会更改索引。

O(m *m *n) 伪代码(其中 m 和 n 是各自数组的长度):

for(int i = 0; i < m - 1; i++)
    for(int j = i + 1; j < m; j++)
        for(int k = 0; k < n; k++)
            if(M[i] + M[j] == N[k] {
                print i, j, k
            }

我正在寻找更优化的解决方案。

谢谢。

Answer 1

将 M 插入哈希数组(哈希集/哈希表)，这样您将获得 O(1) 包含检查。然后迭代 N 中的所有项目，并在此循环内迭代您的哈希集，伪代码:

foreach(integer x in N)
   foreach(integer setY in hashArray)
      if ( hashArray.Contains( x - setY ) )
         then your solution is: setY + (x-setY) = x;

您可以在线性时间内找到这些项目索引。总体运行时间为O(|N|*|M|)。请记住，您可能需要处理极端情况(例如 x = 2*setY)。