Zero_sum的方法效率？(数组) #basic Ruby语言训练营入门准备

Question

我正在为问题#编写一个布尔函数zero_sum？它接受一个整数数组，如果数组中的两个元素之和为零，则返回true。

这是我最初的答案，如果他们要求返回索引，也可以工作，但我在想出一个可以工作的单行函数时遇到了麻烦。

def zero_sum?(array)
  array.each_with_index do |x, i1|
    for i2 in i1 + 1..array.length - 1
      if x + array[i2] == 0
        return true
      end
    end
  end

  false
end

puts "\nZero Sum:\n" + "*" * 15 + "\n"
puts zero_sum?([1, -1]) == true
puts zero_sum?([1,1,0,2,1]) == false
puts zero_sum?([1,1,0,2,1,0]) == true
puts zero_sum?([2,3,4,-3,1]) == true

这是我的单行解决方案。我根本没有得到任何虚假的回报：

def zero_sum?(array)
  array.any? {|x| array.each {|y| array.count(0) != 1 && x + y == 0}}
end

puts "\nZero Sum:\n" + "*" * 15 + "\n"
puts zero_sum?([1, -1]) == true
puts zero_sum?([1,1,0,2,1]) == false  #returning true 
puts zero_sum?([1,1,2,1]) == false  #returning true
puts zero_sum?([1,1,0,2,1,0]) == true
puts zero_sum?([2,3,4,-3,1]) == true

任何洞察力都会很棒！(如果想到返回索引的一行响应，那就太棒了！)

Answer 1

尝尝这个。

require 'set'

def zero_sum?(arr)
  arr.each_with_object(Set.new) do |n,st|
    return true if st.include?(-n)
    st << n
  end
  false
end

zero_sum? [1,-1]        #=> true
zero_sum? [1,1,0,2,1]   #=> false
zero_sum? [1,1,0,2,1,0] #=> true
zero_sum? [2,3,4,-3,1]  #=> true

我让st变成了一个集合而不是数组来提高查找速度。

Answer 2

一种方法是使用Array#combination实现这一点

def zero_sum? arr
  arr.combination(2).any? { |pair| pair.inject(:+).zero? }
end

zero_sum? [2,3,5,2,1,-2,4]    #=> true
zero_sum? [2,3,5,2,1,2,4]     #=> false
zero_sum? [2,3,5,0,0,2,1,2,4] #=> true

关于这个答案的警告是，Array#combination很昂贵，所以可能有更好的方法。不过，了解这种方法还是很有趣的。

非常感谢@Ursus指出使用any?而不是find__。

Answer 3

单行解决方案的问题是，因为any?和each循环遍历整个数组，所以如果没有更早地找到零和，那么每个元素都会在某个时刻被添加到自身。这意味着如果数组包含0，您将得到一个0 + 0 == 0比较。

我不会破坏为您寻找单行代码的工作，但是如果您希望找到一个类似于您的多行代码的解决方案，那么您可以通过创建一个Enumerator并使用with_index来获得当前元素的索引，同时仍然使用any。

array.to_enum.with_index.any? { |x, index| ... }

您可以使用切片表示法访问数组的其余部分：

array[index + 1..array.length - 1]