Сумма двух idx равна нулю. Повторный индекс

Question

Я пишу код для метода, который возвращает сумму пары его индексов, которые добавили результат в ноль. Я все понял, но я столкнулся с ошибкой, которую не смог найти, и сводит меня с ума! При прохождении array = [-1, 0, 2, -2, 1].two_sum (мой метод) возвращаемое значение [[0, 4], [1, 1], [2, 3]] вместо [[0, 4], [2, 3]] (метод сортирует arr в конце). По какой-то причине мой метод принимает idx 1 дважды, хотя, я думаю, я указал в своем коде, что я хочу только сравнить 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

Спасибо за вашу помощь!

Answer 1

Этот код очень трудно понять / поддерживать. Во всяком случае, есть две проблемы:

1. Вы предотвращаете любые действия на idx == comp_idx, а потом сравни idx а также comp_idx + 1
2. Вы повторяете это назад и вперед и, следовательно, дубликаты ([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]]

Answer 2

Если вы в порядке с чем-то простым и рубиновым, вы можете попробовать

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

Answer 3

Поскольку проблема с вашим кодом была идентифицирована, я предложу только другой, более эффективный способ вычисления желаемых пар индексов.

Код

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] #=> 0 за i = 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 # комбинация и Array#product и Enumerable # each_with_object.

Answer 4

Вот другое рабочее решение с использованием комбинации и выберите

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