Solution to LeetCode #1: Two Sum (Python)

Top 0.2% of solutions

This is an easy LeetCode problem (source).

Jump to the solutions ↓

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 <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

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

The obvious solution — O(n²)

At first glance, the solution might jump out at you: loop over the array twice and add the numbers at the current index. Check the result against the target and return.

Let’s write that out.

First we need to loop over the nums list to look at each element in the list.

for i, i_num in enumerate(nums):
    # ...

We use the built-in enumerate function to return the index and value of list items at the same time (read the docs).

Once we’re inside that loop, we need to check the list again so we can get a second number to add to the first.

for i, i_num in enumerate(nums):
    for j, j_num in enumerate(nums):
        # ...

One of the problem requirements stated that we may not use the same element twice. Let’s add some logic to check if we’re looking at the same element and skip to the next element using continue.

if i == j:
    continue