从未排序数组中找到两个元素的最佳方法,其中输入中定义了sum

Question

例如,我有一个未排序的整数数组

array = [ 2,5,3,6,33,11,7,23,8,50,9 ]

通过最小迭代,我如何找到两个总和为10的元素？

方法1:我假设

1. 首先,将另一个数组作为已定义数组的副本.
2. 通过使用For循环,通过添加第一个元素和其余元素来迭代元素,如果我得到10则打破循环.但它会去n次,因为我们没有下一个元素的位置.
3. 在第一次迭代中,如果我没有找到任何元素,那么我将删除所选元素以减少第二次迭代的比较.
4. 以同样的方式,我将使用其余的元素,但再次进行n-1比较.

我尽力找到最好的方法,但没有得到任何解决方案.

Answer 1

您可以通过记住每个值上我们错过的数量来使其大致为O(n):

def foo(array, target = 10)
  h = {}
  array.each do |value|
    return [h[value], value] if h.key?(value)
    h[target - value] = value
  end
  nil
end

foo([ 2,5,3,6,33,11,7,23,8,50,9 ], 10)
=> [3, 7]

我们也可以使用Set,它具有相同的基本流程:

require "set"

def foo(array, target = 10)
  seen = Set.new
  array.each do |value|
    return [target - value, value] if seen.include?(target - value)
    seen << value
  end
  nil
end

foo([ 2,5,3,6,33,11,7,23,8,50,9 ], 10)
=> [3, 7]

这两个选项在幕后是相同的成本(因为Ruby的Set是在Hash之上实现的); 我更喜欢记住我们仍然需要哪个值[以及随之而来的原始值]的语义,但这取决于你找到的哪个更好.

另一个选项是打开array.to_set- 这意味着更多[虽然仍然是线性的]为计算机工作(因为它将整个数组转换为一个集合,而不仅仅是元素,直到它找到匹配),但使代码更简单阅读因为循环只有一个作业:

require "set"

def foo(array, target = 10)
  available = array.to_set
  if match = array.find { |value| available.include?(target - value) }
    [match, target - match]
  end
end

foo([ 2,5,3,6,33,11,7,23,8,50,9 ], 10)
=> [2, 8]

请注意,它找到了一个不同的匹配 - 前一个算法返回第一个匹配,以显示其第二个数字; 新的一个返回第一个匹配,以显示其第一个数字.