Ruby如何返回一对的索引

Question

今天我得到了一个给定数组和'target'的任务,它是该列表中2个整数的总和.一段时间后,我出来了草案解决方案,但它似乎没有通过所有的测试.算法似乎在[0]两次考虑整数.

def two_sum(numbers, target)

numbers.combination 2 do |a, b|
 if a + b == target
  return numbers.index(a), numbers.index(b)
  end
 end
end

print two_sum([1, 2, 3], 4) # Expected [0, 2] *OK

print two_sum([1234, 5678, 9012], 14690) # Expected [1, 2] *OK

print two_sum([2, 2, 3], 4) # Expected [0, 1]) but I get [0, 0] 

我试图首先使用.map而不是.combination(2)方法,但结果完全相同: - /

Answer 1

def two_sum(numbers, target)
  [*0..numbers.size-1].combination(2).find { |i,j| numbers[i] + numbers[j] == target }
end

two_sum([1234, 5678, 9012], 14690)
  #=> [1, 2]
two_sum([1234, 5678, 9012], 14691)
  #=> nil

这是一种更有效的方法,当数组很大时可能会很有用.

require 'set'

def two_sum(arr, target)
  if target.even?
    half = target/2
    first = arr.index(half)
    if first
      last = arr.rindex(half)
      return [first, last] unless last.nil? || first == last
    end
  end
  a1, a2 = arr.uniq.partition { |n| n <= target/2 }
  s = a2.to_set
  n = a1.find { |n| s.include?(target-n) }
  n.nil? ? nil : [arr.index(n), arr.index(target-n)]
end

如果target是甚至我首先检查它的一半是否至少出现两次arr.如果是这样,我们就完成了(除了确定并返回相关索引).即使该方法在该步骤之后没有终止,也需要该步骤不会导致在执行下一步骤之前需要提前终止.

如果target是奇数还是偶数是但它的一半出现小于两倍于arr我构建包含在唯一值的临时数组arr,然后分区成两个阵列,a1包含的值不大于target/2和a2,含有大于值target/2.因此,如果两个数字总和为target1必须在a1,而另一个必须在a2.

为了加快计算我然后转换a2到一组s通过,然后循环a1寻找一个值n,这样的s包含target-n.我们来试试吧.

arr = 100_000.times.map { rand(1_000_000) }

puts "target      i1  arr[i1]     i2  arr[i2]  calc time (secs)"
puts "---------------------------------------------------------"

1000.times do
  t = Time.now
  target = rand(1_000_000)
  i1, i2 = two_sum(arr, target)
  print "#{target} -> "
  print i1.nil? ? "nil                        " :
    "#{i1}  #{arr[i1]}   #{i2}  #{arr[i2]}"
  puts "      #{(Time.now-t).round(4)} secs"
end

版画

target      i1  arr[i1]     i2  arr[i2]  calc time (secs)
---------------------------------------------------------
215113 ->   41   90943   11198  124170      0.027
344479 ->    0   78758   63570  265721      0.0237
188352 ->  190   79209   39912  109143      0.0275
   457 ->  nil                              0.0255
923135 ->   78   84600   43928  838535      0.0207
 59391 ->    2    5779    5454   53612      0.0289
259142 ->   73   58864   29278  200278      0.0284
364486 -> 8049  182243   89704  182243      0.001
895164 ->   13  205843    7705  689321      0.0228
880575 ->   20  440073    6195  440502      0.021

我们看到它arr不包含两个总和的数字457.另外,请注意倒数第三行中的非常短的时间.这是因为target(364486/2 #=> 182243)的一半至少出现了两次arr.