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

I'm doing a ruby problem and my solution works. However, it does not work on bigger test cases because it takes too long to process.

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

The method takes two inputs, an array of numbers and a number.

该方法有两个输入，一个数字数组和一个数字。

The goal is to find the first two numbers in the array whose sum is the number provided in the input.

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

The first pair means that the highest index of the pair is lower than the highest index of any other pairs in the array that add to the number.

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

Example - ([10, 5, 2, 3, 7, 5], 10)

示例 - （[10,5,2,3,7,5]，10）

The answer should be [3, 7] while [5, 5] also sums to 10, the index of the last 5 is 5 and the index of 7 is 4, so [3, 7] comes first.

答案应该是[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

My code worked for all test cases besides those with large arrays.

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

I was wondering if there was a built in method to help or if I needed to loop through the array differently.

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

2 个解决方案

#1

With a Set, only one pass is needed for this problem :

使用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

It outputs the result in the correct order and will be much faster than the other solutions.

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

#2

An alternative approach might be to make sure your combinations are always in the correct order of preference, and then use #find instead of #select. The standard Ruby #combination(2) pairs element 0 with all later elements ([10,5],[10,2],[10,3],[10,7],[10,5]) then pairs index 1 with all later elements ([5,2],[5,3],[5,7],[5,5]) and so forth.

另一种方法可能是确保您的组合始终处于正确的首选顺序，然后使用#find而不是#select。标准Ruby #combination（2）将元素0与所有后面的元素（[10,5]，[10,2]，[10,3]，[10,7]，[10,5]）对，然后对索引1所有后来的元素（[5,2]，[5,3]，[5,7]，[5,5]）等等。

You could write a new modified_combination method that pairs element 1 with all earlier elements ([5,10]) then pairs element 2 with all earlier elements ([2,10],[2,5]), then element 3 ([3,10],[3,5],[3,2]) and so forth. This will ensure the pair with the smallest larger index number is always first in the list.

您可以编写一个新的modified_combination方法，将元素1与所有早期元素（[5,10]）配对，然后将元素2与所有早期元素（[2,10]，[2,5]）配对，然后将元素3配对（[3,10] ，10]，[3,5]，[3,2]）等。这将确保具有最小的较大索引号的对总是在列表中的第一个。

Now you can do:

现在你可以这样做：

x = ints.modified_combination.find { |x, y| x, y == s }.reverse

Remember, this will work most efficiently if modified_combination returns an Enumerator rather than an Array (though it will be much more efficient than your original approach in any case).

请记住，如果modified_combination返回一个枚举器而不是一个数组，这将最有效地工作（尽管在任何情况下它都会比原始方法更有效）。

If you don't want to dig into creating a method that returns an Enumerator, here's a quick-and-dirty solution that achieves the same thing:

如果你不想深入研究创建一个返回枚举器的方法，这里有一个快速而肮脏的解决方案，可以实现同样的目的：

def sum_pairs(ints, s)
  (1...ints.size).each do |x|
    (0...x).each do |y|
      return [ints[y], ints[x]] if ints[x] + ints[y] == s
    end
  end
  nil
end

#1