我正在为一个方法编写代码，该方法返回其添加结果为零的索引对的总和。我已经弄清楚了一切，但是，我遇到了一个我无法找到的错误，让我发疯！ 传递array = [-1, 0, 2, -2, 1].two_sum(我的方法)时，返回值是[[0, 4], [1, 1], [2, 3]]而不是[[0, 4], [2, 3]](该方法在末尾对 arr 进行排序)。出于某种原因，我的方法采用 idx1两次，尽管我认为我已经在我的代码中指定我只想比较idx和idx + 1。
我的代码有什么问题？
这是我到目前为止所拥有的：
class Array
def two_sum
final_arr = []
self.each_with_index do |each, idx|
self.each_index do |comp_idx|
unless comp_idx + 1 == self.length || idx == comp_idx
if (each + self[comp_idx + 1]) == 0
final_arr << [idx, comp_idx + 1].sort
end
end
end
end
final_arr.sort
end
end
感谢您的帮助！
这段代码很难理解/维护。无论如何，有两个问题：
- 您阻止对
idx == comp_idx执行任何操作，然后比较idx和comp_idx + 1 - 你来回迭代它，因此重复项(
[2, 3]和[3, 2]泄漏到结果中。
这是更正后的版本：
class Array
def two_sum
final_arr = []
self.each_with_index do |each, idx|
self.each_index do |comp_idx|
# ⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓⇓
unless comp_idx + 1 == self.length || idx == comp_idx + 1
if (each + self[comp_idx + 1]) == 0
final_arr << [idx, comp_idx + 1].sort
end
end
end
end
# ⇓⇓⇓⇓⇓
final_arr.sort.uniq
end
end
奖励曲目：更惯用的红宝石版本。
▶ arr.each.with_index.with_object([]) do |(e1, idx1), result|
result <<
([idx1].product(
arr[idx1 + 1, arr.length]. # compare only not yet compared
each.
with_index(idx1 + 1). # adjust index
select { |e2, idx2| (e1 ^ -e2).zero? }
))
end.flatten(1).map { |i1, (_, i2)| [i1, i2] }
#⇒ [[0, 4], [2, 3]]
如果你对一些简单而红宝石的东西没问题，你可以试试
arr = [-1, 0, 2, -2, 1]
[*0...arr.size].combination(2).to_a.each_with_object([]) do |a, final_arr|
final_arr << a if arr[a[0]]+arr[a[1]] == 0
end
final_arr.sort
由于您的代码问题已被确定，我只会建议一种不同的、更有效的方法来计算所需的索引对。
法典
def two_sum(arr)
hneg = Hash.new { |h,k| h[k] = [] }
hpos = Hash.new { |h,k| h[k] = [] }
azero = []
arr.each_index do |i|
n = arr[i]
case n <=> 0
when -1 then hneg[-n] << i
when 1 then hpos[n] << i
else azero << i
end
end
(hneg.keys & hpos.keys).each_with_object(azero.combination(2).to_a) { |k,a|
hneg[k].product(hpos[k]) { |pair| a << pair } }
end
例子
two_sum [3, -1, 0, 1, 4, 0, -4, 0, 1]
#=> [[2, 5], [2, 7], [5, 7], [1, 3], [1, 8], [6, 4]]
two_sum [3, -1, 0, 1, 4, 0, -4, 0, -2, -4, 5, 4]
#=> [[2, 5], [2, 7], [5, 7], [1, 3], [6, 4], [6, 11], [9, 4], [9, 11]]
如果[i,j]是返回的数组元素，则arr[i] == arr[j] == 0或arr[i] < 0并arr[j] == -arr[i]。如果需要用i < j写入对，只需编写以下内容。
arr = [3, -1, 0, 1, 4, 0, -4, 0, -2, -4, 5, 4]
two_sum(arr).map { |pair| pair.first > pair.last ? pair.reverse : pair }
#=> [[2, 5], [2, 7], [5, 7], [1, 3], [4, 6], [6, 11], [4, 9], [9, 11]]
解释
步骤如下。
arr = [3, -1, 0, 1, 4, 0, -4, 0, 1]
hneg = Hash.new { |h,k| h[k] = [] }
#=> {}
hpos = Hash.new { |h,k| h[k] = [] }
#=> {}
azero = []
arr.each_index do |i|
n = arr[i]
case n <=> 0
when -1 then hneg[-n] << i
when 1 then hpos[n] << i
else azero << i
end
end
#=> [3, -1, 0, 1, 4, 0, -4, 0, 1]
我们刚刚创建了以下哈希和数组。
hneg
#=> {1=>[1], 4=>[6]}
hpos
#=> {3=>[0], 1=>[3, 8], 4=>[4]}
azero
#=> [2, 5, 7]
这告诉我们arr[1] #=> -1、arr[6] #=> -4、arr[0] #=> 3、arr[3] == arr[8] #=> 1、arr[4] #=> 4和arr[i] #=> 0i = 2, 5, 7。继续
common_keys = hneg.keys & hpos.keys
#=> [1, 4]
这说明hneg和hpos的公用键是[1, 4]。(我们不必担心其他键。
现在计算映射到[0, 0]的所有索引对。
zero_matches = azero.combination(2).to_a
#=> [[2, 5], [2, 7], [5, 7]]
最后，我们获得所需的索引对，如下所示。
common_keys.each_with_object(zero_matches) { |k,a|
hneg[k].product(hpos[k]) { |pair| a << pair } }
#=> [[2, 5], [2, 7], [5, 7], [1, 3], [1, 8], [6, 4]]
请注意，当公用键k => 1时，
k = 1
hneg[k].product(hpos[k])
#=> [[1, 3], [1, 8]]
如果hneg[1] #=> [1, 2]和hpos[1] #=> [3, 4]，我们将得到
hneg[1].product(hpos[1])
#=> [[1, 3], [1, 4], [2, 3], [2, 4]
请参阅类方法 Hash：：new 的形式，该方法采用默认块 Integer#<=>、Array#each_index、Array#combination 和 Array#product 和 Enumerable#each_with_object。
这是使用组合和选择的另一种工作解决方案
class Array
def two_sum
c = (0 .. count-1).to_a.combination(2).to_a
c.select do |i,j|
self[i]+self[j] == 0
end
end
end
a = [-1, 0, 2, -2, 1]
a.two_sum