найти первую комбинацию из двух целых чисел в массиве, чей последний элемент появляется ранними и сумма соответствует заданному значению

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] являются кандидатами для таких комбинаций, но 9 из [1, 9] (который появляется позже, чем в 1array) появляется раньше, чем второй 5 из [5, 5] (который является последним элементом в array). Поэтому я хотел бы вернуть [1, 9].

Я попытался с помощью combination и find:

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

Тем не менее, он возвращает комбинацию первого целого числа в массиве, 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

Я хотел бы использовать 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 2

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

Answer 3

Array#combination(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]