ruby: ¿qué hay de malo con la siguiente matriz y código de sum objective?

Dos sums

  1. Defina un método, two_sum , que acepte una matriz y una sum objective (entero) como argumentos.
  2. El método debe devolver verdadero si hay dos enteros en la sum de la matriz al objective.
  3. De lo contrario, debería devolver falso. Supongamos que la matriz solo contendrá enteros.

 def two_sum(array, target) i = 0 sum = [] while i < array.max i = i + 1 b = i + i sum.push(b) end sum.include?(target) end puts "------Two Sum------" puts two_sum([1,2,3,4,5,6], 8) == true #(im getting true) puts two_sum([1,2,3,4,5,6], 18) == false #(im getting true) puts two_sum([1,3,6], 6) == false #(im getting false) puts two_sum([1,8,2,1], 0) == false #(im getting true) 

Este es un bash de acelerar los cálculos cuando el rendimiento es importante, particularmente cuando la matriz es grande y contiene muchos valores duplicados.

Código

 require 'set' def two_sum(arr, target) return true if target.even? && arr.count(target/2) > 1 st = Set.new arr.uniq.each do |n| return true if st.include?(target-n) st << n end false end 

Ejemplos

 two_sum [1, 4, -4, 4, 5], 6 #=> true two_sum [1, 3, -4, 3, 4], 6 #=> true two_sum [1, 3, -4, 3, 5], 5 #=> false 

Explicación

El código para los valores pares de target tiene dos propósitos:

  • cortocircuita los cálculos cuando la matriz contiene un valor que es igual a la mitad del target , y ese valor aparece al menos dos veces en la matriz; y
  • si el código mencionado anteriormente no devuelve true , permite la eliminación de valores duplicados en arr antes de que se realicen los cálculos restantes.

Para el primer ejemplo los pasos son los siguientes.

 arr = [1, 4, -4, 4, 5] target = 6 target.even? #=> 6.even? => true arr.count(target/2) > 1 #=> arr.count(3) > 1 #=> 1 > 1 #=> false 

así que la true no se devuelve.

 st = Set.new => # b = arr.uniq #=> [1, 4, -4, 5] 

El primer elemento de b ahora se pasa al bloque.

 n = 1 st.include?(target-n) #=> st.include?(6-1) => false as the set is empty st << n #=> # 

Los siguientes pasos son los siguientes.

 n = 4 st.include?(target-n) #=> st.include?(6-4) => false st << n #=> # n = -4 st.include?(target-n) #=> st.include?(6-(-4)) => false st << n #=> # n = 5 st.include?(target-n) #=> st.include?(6-5) => true 

así se devuelve la true .

La solución de Ruby se ve como:

 def two_sum(array, target) array.combination(2).any? { |v| v.reduce(:+) == target } end 

Array#combination devuelve todas las combinaciones de dos elementos y Enumerable#any? devuelve true si el bloque se evalúa como true y false contrario.

Recorres cada elemento de la matriz, lo que es un buen comienzo. Dentro de este bucle, debes intentar sumr cada par de elementos. En este momento, todo lo que está presionando en su matriz de sum es i+i : el índice se duplicó (es decir, cada número par de 0 para duplicar el elemento más grande de su matriz).

Podría intentar sumr cada par de elementos teniendo dos bucles, uno dentro del otro. Ambos iteraban a través de los elementos de la matriz. En su bucle interno, intentaría agregar el elemento actual del bucle externo al elemento actual del bucle interno. Si obtiene alguna coincidencia, puede devolver el valor verdadero y salir inmediatamente; de lo contrario devuelve falso.