1

编写一个方法来确定一个数字数组是否有一对总和为零。注意零的情况；数组中需要有两个零才能组成一个总和为零的对。

下面是我写的代码，但我知道它是错误的。我知道在某个时候它会添加自己，所以如果我的数组中只有一个 0，那么它仍然会返回 true。我是编程和 Ruby 的新手，所以任何建议都会非常感激。

谢谢！

    def has_zero?(array)
        left, right = [-1,1]
        lefter=[]
        righter=[]
        righter=array.each {|x| x+= array[right]}
        lefter=array.each {|x| x+= array[left]}
        if lefter.include?(0) || righter.include?(0)
            return true
        else return false
        end
        left,right = [left-1,right+1]
    end
4

4 回答 4

3

Ruby 有一些内置方法可以让这变得非常简单：

def has_zero_sum_pair?(a)
  a.permutation(2).any?{|pair| pair.inject(:+) == 0}
end

a.permutation(2)给你每一对a。 如果块any?返回，则返回。 是一种获取数组总和的简单方法。truetrueinject(:+)

has_zero_sum_pair?([1, 2, 3])
# => false 
has_zero_sum_pair?([1, 2, 3, -2])
# => true 
has_zero_sum_pair?([1, 2, 3, 0])
# => false 
has_zero_sum_pair?([0, 1, 2, 3, 0])
# => true

更新：如果我不知道Array#permutation并且必须以想到的第一种方式完成此操作，或者如果我担心性能，我可能会做这样的事情：

def has_zero_sum_pair2?(a)
  (0..a.length-2).each do |i|
    (i+1..a.length-1).each do |j|
      return true if a[i] + a[j] == 0
    end
  end
  false
end

我觉得这样更丑更容易出错，而且写起来也花了更长的时间。但是对于小型阵列，它大约快四倍，对于大型阵列，它快 10 倍。编程中通常有一种简单的方法，在大多数情况下工作得很好，但在性能上并不理想。有时，通过选择更好的算法或数据结构，可以在不牺牲清晰度的情况下获得更好的性能。通常必须进行权衡。

更新 2：如果我真的关心性能，我会使用 @FMc 的技术。这是使用更好的数据结构和算法来获得巨大性能提升的一个很好的例子。

于 2013-05-19T17:45:59.850 回答
1

这个问题需要一个Hash.

vals = [0, 4, 3, 0, -3, 2, -2, 1, 3, -4, -4]

# Our hash:
# groups[X] = Array of vals equal to X
groups = vals.group_by { |v| v }

# Just check whether the hash contains a pair
# of keys X and -X, or whether the original array
# had more than one zero in it.
p groups.any? { |k, vs| k == 0 ? vs.size > 1 : groups.has_key?(-k) }

您可以通过稍微更改测试来概括为任何target总和：

k == target / 2 ? vs.size > 1 : groups.has_key?(target - k)
于 2013-05-19T18:47:02.067 回答
1 
array = [1,2,3,-2,0,0]

array.any?{|a| array.rindex(-a) > array.index(a)}

检查是否任何项目的负数在数组中更靠右。（rindex 查找数组中最后一次出现的索引。）

于 2013-05-19T18:57:40.827 回答
1

这工作除了零。

[1, 2, 3, -2]
.uniq.group_by(&:abs).any?{|_, tuple| tuple.length == 2}
# => true
于 2013-05-19T18:00:33.907 回答