14

我正在学习 Ruby，参加伯克利的 MOOC，并且，在这些 MOOC 的一些作业中，我们有一个练习说：

定义一个方法 sum_to_n? 它将一个整数数组和一个附加整数 n 作为参数，如果整数数组中的任何两个元素之和为 n，则返回 true。根据定义，空数组的总和应为零。

我已经创建了两种可以完成这项工作的方法，但我对它们中的任何一种都不满意，因为我认为它们不是用 Ruby 方式编写的。我希望你们中的一些人可以帮助我了解哪种方法是正确的！

我制作的第一个方法对两次迭代都使用了该each方法，但我不喜欢这种方法的是每个数字都与其他数字相加，即使是相同的数字，做这样的事情：

arr[1, 2, 3, 4] => 1+1, 1+2, 1+3, 1+4, 2+1, 2+2, 2+3, 2+4, 3+1, 3+2... 4+3, 4+4

正如你所看到的，有很多重复的总和，我不希望这样。

这是代码：

def sum_to_n?(arr, n)
  arr.each {|x| arr.each {|y| return true if x + y == n && x != y}}
  return true if n == 0 && arr.length == 0
  return false
end

用另一种方法，我得到了我想要的，只是几个总和而不重复任何一个，甚至不加相同的数字，但它看起来很可怕，我很确定有人会因为这样做而杀了我，但是如您所见，该方法做得很好：

arr[1, 2, 3, 4] => 1+2, 1+3, 1+4, 2+3, 2+4, 3+4

这是代码：

def sum_to_n?(arr, n)
  for i in 0..arr.length - 1
    k = i + 1
    for k in k..arr.length - 1
      sum = arr[i] + arr[k]
      if sum == n
        return true
      end
    end
  end
  return true if n == 0 && arr.length == 0
  return false
end

好吧，我希望你们能像我尝试的那样做一个更好、更漂亮的方法。

谢谢您的帮助。

4

7 回答 7

22

我会这样写：

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?
  arr.combination(2).any? {|a, b| a + b == n }
end

这似乎是一个非常 Rubyish 的解决方案。

于 2013-10-15T00:46:18.427 回答
5

我在CodeWars上遇到了这个。公认的答案确实看起来非常 Rubyish，但这是以性能为代价的。调用arr.combination(2)会产生很多组合，逐个元素遍历数组并搜索“补码”是否sum - element存在会更简单。这就是它的样子 -

def sum_to_n?(arr, n)
  (arr.empty? and n.zero?) or arr.any? { |x| arr.include?(n - x) }
end
于 2015-05-03T10:11:07.000 回答
2

除了@jorg-w-mittag 的答案。我找到了另一个使用“排列”的解决方案。

https://stackoverflow.com/a/19351660/66493

def sum_to_n?(arr, n)
  (arr.empty? && n.zero?) || arr.permutation(2).any? { |a, b| a + b == n }
end

我以前不知道置换。仍然喜欢@jorg-w-mittag 答案，因为它更具可读性。

于 2013-10-31T19:55:56.310 回答
1

这个将在O(n.log(n))而不是O(n²)：

a = 1, 2, 3, 4

class Array
  def sum_to? n
    unless empty?
      false.tap {
        i, j, sorted = 0, size - 1, sort
        loop do
          break if i == j
          a, b = sorted[i], sorted[j]
          sum = a + b
          return a, b if sum == n
          sum < n ? i += 1 : j -= 1
        end
      }
    end
  end
end

a.sum_to? 7 #=> [3, 4]
于 2013-10-15T01:22:10.683 回答
0

我喜欢https://stackoverflow.com/a/30012616/8706387但是当 n 加倍 x 时它会失败。我们应该在发送之前从数组中删除 x include? n - x。

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?
  arr.any? { |x| arr.tap { arr.delete_at arr.index x }.include? n - x }
end
于 2021-10-10T14:53:04.583 回答
0

我有一个想法，这个问题的任何答案的开始可能应该从修剪数组以获取多余数据开始：

不能用这个：

  arr.select! { |e| e <= n } # may be negative values

但这可能会有所帮助：

  arr.sort!
  while arr[0] + arr[-1] > n # while smallest and largest value > n
    arr.delete_at(-1) # delete largest vaue
  end
于 2017-11-10T10:11:31.180 回答
0

我想知道为什么这里没有答案使用hash？

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?

  h = {}
  arr.any? { |x| complement = h[n-x]; h[x] = true; complement }
end

puts sum_to_n?([1,2,3,4,5,7], 6) # true
puts sum_to_n?([6,2,3,5,7,9], 6) # false
puts sum_to_n?([3,4,5,3], 6) # true
puts sum_to_n?([3,4,5,7], 6) # false
puts sum_to_n?([], 6) # false
puts sum_to_n?([], 0) # true
于 2021-10-11T03:13:32.967 回答