Как повысить эффективность алгоритма для вложенного цикла

Question

Учитывая список целых чисел и одно значение суммы, верните первые два значения (слева), которые складываются, чтобы сформировать сумму.

Например, учитывая:

sum_pairs([10, 5, 2, 3, 7, 5], 10)

[5, 5] (по индексам [1, 5] из [10, 5, 2, 3, 7, 5]) - до 10, а [3, 7] (по индексам [3, 4]) - до 10.Среди них вся пара [3, 7] является более ранней и, следовательно, является правильным ответом.

Вот мой код:

def sum_pairs(ints, s)
  result = []
  i = 0
  while i < ints.length - 1
    j = i+1
    while j < ints.length
      result << [ints[i],ints[j]] if ints[i] + ints[j] == s
      j += 1
    end
    i += 1
  end
  puts result.to_s
  result.min
end

Это работает, но слишком неэффективно, занимая 12000 мсбежать.Вложенный цикл - это проблема неэффективности.Как я могу улучшить алгоритм?

Answer 1

Один вкладыш (самый быстрый?)

ary = [10, 0, 8, 5, 2, 7, 3, 5, 5]
sum = 10

def sum_pairs(ary, sum)
  ary.map.with_index { |e, i|  [e, i] }.combination(2).to_a.keep_if { |a| a.first.first + a.last.first == sum }.map { |e| [e, e.max { |a, b| a.last <=> b.last }.last] }.min { |a, b| a.last <=> b.last }.first.map{ |e| e.first }
end

Да, он не совсем читабелен, но если вы добавляете методы шаг за шагом, начиная с ary.map.with_index { |e, i| [e, i] }, легко понять, как это работает.

Answer 2

require 'set'

def sum_pairs(arr, target)
  s = Set.new
  arr.each do |v|
    return [target-v, v] if s.include?(target-v)
    s << v
  end
  nil
end

sum_pairs [10, 5, 2, 3, 7, 5], 10
  #=> [3, 7]
sum_pairs [10, 5, 2, 3, 7, 5], 99
  #=> nil

Я использовал Установить методы для ускорения include? поиска (и, что менее важно, для сохранения только уникальных значений).

Answer 3

Попробуйте ниже, так как это гораздо более читабельно.

def sum_pairs(ints, s)
  ints.each_with_index.map do |ele, i|
    if ele < s
      rem_arr = ints.from(i + 1)
      rem = s - ele
      [ele, rem] if rem_arr.include?(rem)
    end
  end.compact.last
end

Answer 4

• У вас есть Set чисел, которые вы видели, начиная с пустого
• Посмотрите на каждое число в списке ввода
• Подсчитайте, какое число вам нужно добавить к немусоставляют сумму
• Посмотрите, есть ли это число в наборе
• Если это так, верните его, и текущий элемент
• Если нет, добавьте текущий элемент кустановить и продолжить цикл
• Когда цикл заканчивается, вы уверены, что такой пары нет;в задаче не указано, но возвращение nil, вероятно, является наилучшим вариантом

Должно идти очень быстро, поскольку существует только один цикл.Он также завершается, как только он находит первую подходящую пару, поэтому обычно вы даже не пройдете через каждый элемент, прежде чем получите свой ответ.

Как стиль, использование while таким образом оченьunRubyish.При реализации вышеизложенного я предлагаю вам использовать ints.each do |int| ... end вместо while.

РЕДАКТИРОВАТЬ: Как прокомментировал Кэри Свовеланд, по странной причине я подумал, что вам нужны индексы, а не значения.