Leetcode dos suma
Actualmente estoy aprendiendo c ++ procedente de Python, así que incluiré una solución en Python y en C ++ para la siguiente declaración del problema:
Dada una matriz de números enteros y un objetivo entero, devuelve índices de los dos números de manera que se sumen al objetivo. Puede suponer que cada entrada tendría exactamente una solución y no puede usar el mismo elemento dos veces. Puede devolver la respuesta en cualquier orden.
Ejemplo 1:
Entrada: nums = [2,7,11,15], objetivo = 9
Salida: [0,1]
Ejemplo 2:
Entrada: nums = [3,2,4], target = 6
Resultado: [1,2]
Me gustaría escuchar sus comentarios / sugerencias para mejorar el rendimiento / otras sugerencias. Aqui esta el enlace
two_sum.py
def two_sum(nums: list, target: int):
for i, n in enumerate(nums):
match = target - n
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
if __name__ == '__main__':
if result := two_sum([2, 7, 11, 15], 22):
print(f'Indices:\n{result}')
else:
print('No matches found')
Estadísticas de Leetcode:
Tiempo de ejecución: 772 ms, más rápido que el 36,98% de los envíos en línea de Python para Two Sum. Uso de memoria: 14,4 MB, menos del 49,82% de los envíos en línea de Python para Two Sum.
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
vector<int> two_sum_solution(vector<int> &nums, int target) {
vector <int> results;
for (int i = 0; i < nums.size(); ++i) {
int match = target - nums[i];
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] == match) {
for (int index_match : {
i, j
})
results.push_back(index_match);
}
}
}
return results;
}
#endif //LEETCODE_TWO_SUM_H
main.cpp
#include <vector>
#include "two_sum.h"
using std::vector;
int main() {
vector<int> v1{2, 7, 11, 15};
vector<int> v = two_sum_solution(v1, 22);
if (!v.empty()) {
cout << "Indices:" << endl;
for (auto i: v)
cout << i << " ";
}
else (cout << "No matches found");
}
Estadísticas de Leetcode:
Tiempo de ejecución: 384 ms, más rápido que el 34,03% de los envíos en línea de C ++ para Two Sum. Uso de memoria: 9,3 MB, menos del 12,99% de los envíos en línea de C ++ para Two Sum.
Respuestas
No soy un experto en C ++ pero puedo dar un comentario sobre la solución Python.
Su solución actual se ejecuta en \$O(n^2)\$. Básicamente, para cada número nde la entrada nums, busque target - nen nums. ¿Cómo mejorarlo?
La segunda parte del algoritmo se puede mejorar desde \$O(n)\$a \$O(1)\$. En lugar de buscar target - nen una lista, puede usar un diccionario:
def two_sum(nums: list, target: int):
num_index = {}
for i, n in enumerate(nums):
match = target - n
if match in num_index:
return num_index[match], i
num_index[n] = i
return -1
Resultados:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB
Incluya solo los archivos de encabezado que necesita
En su two_sum.harchivo, no es necesario iostream, ya que no está utilizando ninguna de sus funciones. Recuerde que, #includeliteralmente, copiar y pegar el archivo, por lo que si incluye este archivo de encabezado en varios archivos, podría ralentizar los tiempos de compilación.
Declaraciones y definiciones divididas
Normalmente, dividiría sus archivos en dos partes: el archivo de encabezado (normalmente termina con *.h, *.hpp, *.hh) y el archivo de origen (normalmente termina con *.cpp, *.cc). El archivo de encabezado solo consta de las declaraciones y el archivo de origen contiene la implementación.
Entonces, en su caso, su archivo de encabezado se verá así:
two_sum.h
#ifndef LEETCODE_TWO_SUM_H
#define LEETCODE_TWO_SUM_H
#include <vector>
std::vector<int> two_sum_solution(std::vector<int> &nums, int target);
#endif // LEETCODE_TWO_SUM_H
y su archivo fuente se verá así:
two_sum.cpp
#include "two_sum.h"
std::vector<int> two_sum_solution(std::vector<int> &nums, int target)
{
...
}
De hecho, si intenta incluir su two_sum.h(con la implementación) en varios archivos, estaría rompiendo la regla de una definición . Sus archivos de origen contendrían múltiples definiciones de la misma función y el vinculador arrojará un error. Una forma de moverse es marcar las funciones inline, pero lo más probable es que desee hacer lo primero.
No using namespaceen los archivos de encabezado
No haga using namespaceni ninguna de sus variantes en un archivo de encabezado. Dado que el archivo de encabezado se copia y pega en varios archivos de origen, tiene el potencial de causar errores molestos. Mira aquí
Usar referencia constante
Como two_sum_solutionno modifica el numsvector, páselo por referencia constante.
size_t vs int para índices de matriz
Considere usar size_t en lugar de int para índices de matriz
Use autotanto como sea posible
Hay un par de instancias en su código donde puede usar en autolugar de especificar el tipo. Ejemplos:
auto match = target - nums[i];
auto v = two_sum_solution(v1, 22);
El bucle más interno no tiene sentido
Simplemente haz
results.push_back(i);
results.push_back(j);
Además, una vez que haya encontrado la solución, es posible que desee devolver el resultado de inmediato.
Quizás pueda mejorar el rendimiento creando un mapa de valor -> índice en la primera iteración sobre la matriz dada.
Actualmente, su programa hace lo siguiente (complejidad de tiempo):
- iterar sobre todos los
index, valuepares de la matriz ( \$ O(n) \$) - buscar
target - valueen la matriz ( \$ O(n) \$) - índice de búsqueda de
target - value( \$ O(n) \$)
Y como todos están anidados, se llega a \$ O(n^2) \$(no es \$ n^3 \$ porque la última búsqueda no se realiza para cada iteración).
Mi solución propuesta:
- Crea un mapa / dictado de
{value: index}( \$ O(n) \$) - Iterar sobre la
index, valuematriz ( \$ O(n) \$) - Buscar y devolver el índice del mapa / dict ( \$ O(1) \$)
def two_sum(numbers: list[int], target: int):
lookup: dict = {
value: index
for index, value in enumerate(numbers)
}
for index, value in enumerate(numbers):
match = target - value
if search_index := lookup.get(match):
return index, search_index
return None
Esto es interesante para mí porque vengo de C y comencé a usar Python en los últimos años para trabajar, así que tuve el camino inverso como tú. Cuando comencé Python, prefería soluciones como la suya porque recorrer las listas es muy explícito y claro.
Sin embargo, desde entonces aprendí que los programadores de Python más competentes en el trabajo entienden mejor mi código cuando uso la biblioteca estándar. Una vez que comencé a invertir en aprender esas herramientas, tuvo el doble efecto de 1) hacer mi código más conciso y 2) ser más eficiente en tiempo y / o espacio.
En este caso, resolvería el problema con combinationsel itertoolspaquete:
from itertools import combinations
def two_sum(nums, target):
pairs_with_indices = combinations(enumerate(nums), 2)
# result is a generator comprehension.
winning_pairs = ((index_i, index_j)
for (index_i, i), (index_j, j) in pairs_with_indices
if sum((i, j)) == target)
# Insert as much error checking as you need...
return next(winning_pairs)
Probablemente haya una solución aún mejor, más concisa y clara usando Numpy, que es efectivamente una biblioteca estándar en mi línea de trabajo (ciencia de datos), pero eso no es cierto en todas partes.
Una cosa que es diferente a su código: no hay lugar para errores uno por uno. En mi experiencia, un código como este
if match in (rest := nums[i + 1:]):
match_at = rest.index(match)
return i, match_at + i + 1
para mí es fácil de escribir, difícil de leer y la facilidad de mantenimiento abarca todo el gambito de fácil a imposible. En otras palabras, administrar índices manualmente en Python me da la cuerda suficiente para colgarme, y las funciones de biblioteca estándar han sido una gran alternativa.
Conoce tus contenedores
std::unordered_mapes tu amigo en este problema. Siempre que nunca haya visto un número, simplemente use la función operator[]o insertpara sumar el número y su índice. Cuando se usa find, devolverá un iterador, que es un key-valuepar.
p.ej:
auto location = m.find(numToFind);
location->firstes tu clave y
location->secondes tu valor
Cuando regrese, no use push_back
Simplemente puede devolver una lista de inicialización como: {i,j}.