哈希将彼此的每个值相加

Question

我有一个哈希，如下所示：

hash = {
  "Hulk" => 25,
  "IronMan" => 75,
  "Groot" => 51,
  "Captain America" =>50,
  "Spider Man" => 40,
  "Thor" => 50,
  "Black Panther" => 49
}

我需要找到一组超级英雄，当我与对方的价值相加时，其价值将为100，例如，美国队长+托尔= 100。

我可以使用索引遍历带有索引的哈希：

hash.each_with_index { |(key,value),index| ... }

用内循环比较每个值。

有没有更好，更简单的方法来解决这个问题？

Answer 1

如果输入不是很大，可以使用Array#combination：

1.upto(input.size).
  flat_map do |i|
    input.to_a.combination(i).select do |arrs|
      arrs.map(&:last).reduce(:+) == 100
    end
  end.
  map(&:to_h)
#⇒ [{"Hulk"=>25, "IronMan"=>75},
#   {"Groot"=>51, "Black Panther"=>49},
#   {"Captain America"=>50, "Thor"=>50}]

---

如果你确定只有2个英雄的力量总和到100，用1.upto(input.size)的论据替换2循环与硬编码的combination。在这种情况下，即使对于巨大的输入，它也足够快。

Answer 2

你可以实现线性复杂性O(N)性能明智

编辑我认为你正在寻找2的组合，这是不正确的，据我所知。

input = { 
  "Hulk" => 25,
  "IronMan" => 75,
  "Groot" => 51,
  "Captain America" => 50,
  "Spider Man" => 40,
  "Thor" => 50,
  "Black Panther" => 49
}

# Create inverse lookup map
inverse_input = input.each.with_object(Hash.new([])){ |(k, v), h| h[v] += [k] }
#=> {25=>["Hulk"], 75=>["IronMan"], 51=>["Groot"], 50=>["Captain America", "Thor"], 40=>["Spider Man"], 49=>["Black Panther"]}

input.flat_map do |hero, power| 
  # Get heroes with needed power only
  other_heroes = inverse_input[100 - power]
  # Remove current hero from the list
  other_but_this = other_heroes.reject{ |name| name == hero }
  # Map over remaining heroes 
  # and sort them for later `uniq` filtering
  other_but_this.map { |h| [hero, h].sort }
end.compact.uniq
# compact will remove nils
# uniq will remove duplicates
#=> [["Hulk", "IronMan"], ["Black Panther", "Groot"], ["Captain America", "Thor"]]

如果输入的长度很小，你可以使用更短的O(N^2)解决方案：

input.to_a.
      permutation(2).
      select{|(n1,v1), (n2, v2)| n1 != n2 && v1 + v2 == 100 }.
      map{ |l,r| [l.first, r.first].sort }.
      uniq
#=> [["Hulk", "IronMan"], ["Black Panther", "Groot"], ["Captain America", "Thor"]]

Answer 3

一个潜在的解决方案是：

all_options = input.map { |a| input.without(a).map { |b| [a, b] } }.flatten(1).sort.uniq

valid_options = all_options.select { |r| r.sum(&:second) == 100 }

修正案，第一行可以使用input.combination(2)（oops）来实现。整个问题可以通过以下方式解决：

input.combination(2).select { |r| r.sum(&:second) == 100 }.map(&:to_h)

Answer 4

我猜这就是你要找的东西

resultArr = []
input.keys.each do |keyName|
  input.each do |inKey, inValue|
    ((resultArr << [keyName, inKey]) if ((input[keyName] + inValue) == 100)) unless (keyName == inKey)
  end
end

result = []
resultArr.each do |resArr| result << resArr.sort end
result.uniq!
puts result

Answer 5

尝试

input["Thor"] + input["Captain America"]

您创建的输入对象是一个哈希值，从哈希值中获取值的最简单方法是输入与之关联的键：

hash["key"]