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

Question

Я нахожусь в процессе обучения рубина, принимая Mooc Беркли, и, в некоторых из этих домашних заданий 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 

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

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

Answer 1

Я бы написал так:

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

Это кажется довольно Rubyish решение.

Answer 2

Это один будет делать это в 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] 

Answer 3

рядом с @ Йорг-W-Миттаг- в. Я нашел другое решение, используя «перестановку».

https://stackoverflow.com/a/19351660/66493

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

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

Answer 4

Я наткнулся на это на CodeWars. accepted answer уверен, что выглядит очень рубиновым, но это ценой производительности.Вызов 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 

Answer 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