在数组中我们如何找到2个元素在给定数字中的差异..？少于O(n ^ 2)时间

Question

可能重复:
检查2个数组是否与I相加

我的问题是我有一个给定的数字no=10;假设和一个数组A,我必须找到那些没有谁的差异是给定的没有.例如: - A[5]-A[3]=10;然后打印print(A[5]); Print(A[5])
我有一个算法,O(n^2)及时做到但我们需要更好的东西...
我的直觉可能是在做短暂的数组之后做的事情.....但是如何...因为在做空之后还需要两个循环来检查那个条件......
我有点困惑......

Answer 1

原始答案 - O(n log n)

怎么样:

• 对数组(或副本)进行排序.这是O(n log n)
• 迭代数组,并为每个值x进行二进制搜索x + no
  • 每个二进制搜索都是O(log n)
  • 总体O(n log n)

总成本:O(n log n)

根据Steve Jessop的评论修改上述内容:

FWIW,您不必对x + no进行二进制搜索.在迭代数组时,可以在第一个迭代点之前保持第二个迭代点.由于对数组进行了排序,因此在每个步骤中x + no大于或等于上一步中x + no的值,因此从上一步开始的第二个迭代点开始的线性搜索只会前进,因此是O (n)整个外部迭代的总和,即使对于n个步骤中的每个步骤都不是O(1).

这仍然需要预先排序,但是O(n log n).

最佳答案IMO(易于实施和O(n))

编辑:或者,当然,构建一个HashSet以更快地进行包含检查(假设创建集合是分摊O(n)并且查找是O(1)):

HashSet<int> values = new HashSet<int>(array);
foreach (int value in array)
{
    if (values.Contains(value + no))
    {
        // Found a match
    }
}