Ruby - 添加到特定给定输入的数组中的对的总和

Question

我正在做一个红宝石问题,我的解决方案有效.但是,它不适用于更大的测试用例,因为处理时间太长.

该方法需要两个输入,一个数字数组和一个数字.

目标是找到数组中的前两个数字,其总和是输入中提供的数字.

第一对意味着该对的最高索引低于数组中添加到该数字的任何其他对的最高索引.

示例 - ([10,5,2,3,7,5],10)

答案应该是[3,7],而[5,5]也总和为10,最后5的索引是5,索引7是4,所以[3,7]首先出现.

def sum_pairs(ints, s)
  return nil if ints.empty? || ints.nil?

  x = ints.combination(2).select {|x, y| x + y == s}

  return nil if x.nil? || x.empty?

  ints.rindex(x[0][1]) > ints.rindex(x[-1][1]) ? x.last : x.first 

end

我的代码适用于除大型数组之外的所有测试用例.

我想知道是否有一个内置的方法来帮助或者我是否需要以不同的方式循环遍历数组.

Answer 1

使用a Set,此问题只需要一次传递:

require 'set'

def sum_pairs(ints, s)
  already_seen = Set.new
  ints.each do |int|
    return [s - int, int] if already_seen.include?(s - int)
    already_seen.add(int)
  end
  nil
end

sum_pairs([10, 5, 2, 3, 7, 5], 10)
# [3, 7]
sum_pairs([10, 5, 2, 3, 7, 5], 20)
# nil

它以正确的顺序输出结果,并且比其他解决方案快得多.