Руби, как вернуть индекс пары

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. Отсюда следует, что если сумма двух чисел равна target, то одно должно быть в 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. Также обратите внимание на очень короткое время в предпоследнем ряду. Это связано с тем, что один * helf из target (364486/2 #=> 182243) появляется как минимум дважды в arr.