Как создать вложенный цикл с Ruby "Правильный путь!"?

Я изучаю Ruby, беру MOK Беркли, и в некоторых из этих домашних заданий MOOC у нас есть упражнение, в котором говорится:

Определить метод sum_to_n? который принимает массив целых чисел и дополнительное целое число, n, как аргументы и возвращает true, если любые два элементы в массиве целых чисел суммируются с n. Пустой массив должен суммировать к нулю по определению.

Я уже создал два метода, которые могут выполнять эту работу, но мне не нравится ни один из них, потому что я думаю, что они не написаны на Ruby Way. Я надеюсь, что некоторые из вас помогут мне узнать, что будет правильным!

Первый метод, который я использовал, использует метод each для обеих итераций, но то, что мне не нравится в этом методе, состоит в том, что каждое число суммируется с любым другим числом, даже с тем же числом, что-то вроде этого:

arr[1, 2, 3, 4] => 1+1, 1+2, 1+3, 1+4, 2+1, 2+2, 2+3, 2+4, 3+1, 3+2... 4+3, 4+4

Как вы можете видеть, много повторных сумм, и я не хочу этого.

Это код:

def sum_to_n?(arr, n)
  arr.each {|x| arr.each {|y| return true if x + y == n && x != y}}
  return true if n == 0 && arr.length == 0
  return false
end

С помощью другого метода я получил то, что хотел, всего несколько сумм, не повторяя ни одного из них или даже суммируя одинаковые числа, но он выглядит УЖАСНЫМ, и я уверен, что кто-то захочет убить меня за это но метод делает отличную работу, как вы можете видеть:

arr[1, 2, 3, 4] => 1+2, 1+3, 1+4, 2+3, 2+4, 3+4

Это код:

def sum_to_n?(arr, n)
  for i in 0..arr.length - 1
    k = i + 1
    for k in k..arr.length - 1
      sum = arr[i] + arr[k]
      if sum == n
        return true
      end
    end
  end
  return true if n == 0 && arr.length == 0
  return false
end

Хорошо, надеюсь, вы, ребята, повеселитесь, делая лучший и красивый метод, как я пытался.

Благодарим вас за помощь.

Ответ 1

Я бы написал его вот так:

def sum_to_n?(arr, n)
  return true if arr.empty? && n.zero?
  arr.combination(2).any? {|a, b| a + b == n }
end

Это похоже на довольно рубиновое решение.

Ответ 2

Я наткнулся на это на CodeWars. принятый ответ уверен, что выглядит очень рубиновым, но это связано с производительностью. Вызов arr.combination(2) приводит к множеству комбинаций, было бы проще переходить через элемент массива по элементу и искать, существует ли 'дополнение' sum - element. Вот как это будет выглядеть -

def sum_to_n?(arr, n)
  (arr.empty? and n.zero?) or arr.any? { |x| arr.include?(n - x) }
end

Ответ 3

Рядом с @jorg-w-mittag ответ. Я нашел другое решение, используя "перестановку".

fooobar.com/questions/410493/...

def sum_to_n?(arr, n)
  (arr.empty? && n.zero?) || arr.permutation(2).any? { |a, b| a + b == n }
end

Раньше я не знал о перестановке. По-прежнему нравится @jorg-w-mittag, потому что он более читабельный.

Ответ 4

Это будет сделано в O(n.log(n)), а не O(n²):

a = 1, 2, 3, 4

class Array
  def sum_to? n
    unless empty?
      false.tap {
        i, j, sorted = 0, size - 1, sort
        loop do
          break if i == j
          a, b = sorted[i], sorted[j]
          sum = a + b
          return a, b if sum == n
          sum < n ? i += 1 : j -= 1
        end
      }
    end
  end
end

a.sum_to? 7 #=> [3, 4]

Ответ 5

У меня возникла мысль, что начало любого ответа на этот вопрос должно начинаться с обрезки массива для лишних данных:

Нельзя использовать это:

  arr.select! { |e| e <= n } # may be negative values

Но это может помочь:

  arr.sort!
  while arr[0] + arr[-1] > n # while smallest and largest value > n
    arr.delete_at(-1) # delete largest vaue
  end