查找数组中后一个元素最早出现且总和与给定值匹配的两个整数的第一个组合

Question

我有 array 和 sum_of_two:

array = [10, 5, 1, 9, 7, 8, 2, 4, 6, 9, 3, 2, 1, 4, 8, 7, 5]
sum_of_two = 10

我试图在 array 中找到两个整数的组合，这两个整数的后一个元素在总和等于 sum_of_two 的组合中最早出现。例如，[5, 5] 和 [1, 9] 都是此类组合的候选，但是 [1, 9] 的 9（出现在 array 中的 1 之后）出现早于 [5, 5] 的第二个 5（这是 array 中的最后一个元素）。所以我想 return [1, 9].

我尝试使用 combination 和 find:

array.combination(2).find{|x,y| x + y == sum_of_two} #=> [5, 5]

但是，它 return 是数组中第一个整数 5 和数组后面的另一个整数 5 的组合。

如果我使用 find_all 而不是 find，我会得到两个整数的所有组合，加起来等于 sum_of_two:

array.combination(2).find_all{|x,y| x + y == sum_of_two}
#=> [[5, 5], [1, 9], [1, 9], [9, 1], [7, 3], [8, 2], [8, 2], [2, 8], [4, 6], [6, 4], [9, 1], [3, 7], [2, 8]]

但是我不确定如何获得第一个。

Answer 1

x = array.find.with_index{|e, i| array.first(i).include?(sum_of_two - e)}
[sum_of_two - x, x] # => [1, 9]

Answer 2

我会使用 Set（这比使用 Array#include? 更有效）并执行如下操作：

array = [10, 5, 1, 9, 7, 8, 2, 4, 6, 9, 3, 2, 1, 4, 8, 7, 5]
sum_of_two = 10

require 'set'

array.each_with_object(Set.new) do |element, set| 
  if set.include?(sum_of_two - element)
    break [sum_of_two - element, element]
  else
    set << element
  end
end
#=> [1, 9]

Answer 3

Array#combination(n) 没有按照您想要的顺序给出元素，因此您必须自己构建对。如果您从第二个索引开始，这很容易。 O(n) 惰性实现，让我们调用输入 xs:

pairs = (1...xs.size).lazy.flat_map { |j| (0...j).lazy.map { |i| [xs[i], xs[j]] } }
first_matching_pair = pairs.detect { |i, j| i + j == 10 }
#=> [1, 9]

查找数组中后一个元素最早出现且总和与给定值匹配的两个整数的第一个组合

Finding the first combination of two integers in an array whose latter element appears the earliest and sum matches a given value

ruby

arrays

combinations