Two Sum

Contents

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

My Solution

Solving the problem is easy once you realize that you don’t need to sum every pair in the array, but rather for each element in the array calculate the difference to the target value and if the difference is present in the array, jackpot, now you have two numbers that sum to the target.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevs = {}
        for i, num in enumerate(nums):
            if (num in prevs):
                return [prevs[num], i]

            prevs[target - num] = i

        return []

Si te gusta el contenido, por favor apoya mi trabajo!

Donar en GitHub Donar en Patreon

Juan Cruz Martinez

¡Hola!

Soy Juan Cruz Martinez, el fundador de LiveCodeStream.dev. Me encanta programar y creo en el poder de la programación no solo para construir un mundo mejor, sino para hacer que TU vida sea mejor.

Fundé LiveCodeStream.dev porque quería ayudarte a aprender a programar, construir una mejor carrera y, en última instancia, crear una vida mejor. Eso me sucedió hace más de una década cuando comencé a programar, y le sucede a decenas de miles de personas a diario. Quiero que TÚ te unas a esa revolución.

No importa cómo lo llames, escribir código, programación, desarrollo de software o cualquier otra cosa, las habilidades involucradas están en una demanda cada vez mayor. Y ya sea que quieras incursionar en el desarrollo de sitios web, diseño de juegos, desarrollo de blockchain o cualquier otra cosa, quiero ayudarte.