[LeetCode] 1. Dos sumas

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Fácil

Dada una serie de números enteros números y un numero entero objetivo, devolver índices de los dos números tales que suman objetivo.

Puede suponer que cada entrada tendría exactamente una solución, y no podrá utilizar el mismo elemento dos veces.

Puede devolver la respuesta en cualquier orden.

Ejemplo 1:

Aporte: números = [2,7,11,15], objetivo = 9
Producción: [0,1]
Explicación: Como nums[0] + nums[1] == 9, devolvemos [0, 1].

Ejemplo 2:

Aporte: números = [3,2,4], objetivo = 6
Producción: [1,2]

Ejemplo 3:

Aporte: números = [3,3], objetivo = 6
Producción: [0,1]

Restricciones:

2 <= números.longitud <= 10 ⁴
-10 ⁹ <= números[i] <= 10 ⁹
-10 ⁹ <= objetivo <= 10 ⁹
Sólo existe una respuesta válida.

Hacer un seguimiento: ¿Puedes idear un algoritmo que sea menor que O(n ² ) ¿complejidad del tiempo?

Pitón

				
					al escribir import List # fuerza bruta # complejidad del tiempo: O(n^2) # complejidad del espacio: O(1) clase Solución: def twoSum(self, nums: List[int], target: int) -> List[int] : para i en rango(len(nums)): para j en rango(i + 1, len(nums)): si nums[j] == objetivo - nums[i]: devuelve [i, j] # hashMap # Complejidad del tiempo: O(n) # Complejidad del espacio: O(1) clase Solución(objeto): def twoSum(self, nums: List[int], target: int) -> List[int]: numMap = {} for i , num en enumerar(nums): complemento = objetivo - num si complemento en numMap: return [numMap[complemento], i] numMap[num] = i devuelve [] # dos punteros # complejidad de tiempo: O(n) # complejidad de espacio : O(1) clase Solución(objeto): def twoSum(self, nums: List[int], target: int) -> List[List[int]]: res = [] izquierda, derecha = 0, len(nums ) - 1 mientras (izquierda < derecha): currSum = nums[izquierda] + nums[derecha] si currSum < objetivo o (izquierda > 0 y nums[izquierda] == nums[izquierda - 1]): izquierda += 1 elif currSum > target o (right < len(nums)-1 and nums[right] == nums[right + 1]): right -= 1 else: res.append([nums[left], nums[ derecha]]) izquierda += 1 derecha -= 1 return res nums = [2, 7, 11, 15] objetivo = 9 solución = Solución() resultado = solución.dosSuma(nums, objetivo) imprimir(resultado)

Fácil

Pitón

Artículos relacionados