Python: Prevent double for-loop from returning same indexes of list

Question

I am currently working on problem 1 in Leetcode, named "Two Sum."

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

My current code is:

def twosum_indices(nums, target):
    for i in nums:
        for v in nums[i + 1:]:
            if i + v == target:
                return nums.index(i), nums.index(v)

In this, nums is a list of integers, and the program must return two different indexes in a list, such that their true values add up to a given target. Although this works fine on most test cases, it fails on a list like [3,3] where both values are the same, and returns the same index twice, like [0,0] instead of returning the actual answer of [0,1]. Why is this happening?

Answer 1

There are multiple bugs in your code, not the least of which is a failure to use enumerate instead of list.index. For example, [3, 3].index(3) is of course always 0.

The focus of this answer is not to arrive at the most efficient solution, but to improve upon your specific approach. You can alternatively see the the O(n) solution instead.

Understanding list comprehensions

As a prerequisite, first understand how multiple for loops can exist in a list comprehension.

def sums(nums):
    return [x + y for x in nums for y in nums[:x]]

The above is equivalent to:

def sums(nums):
    output = []
    for x in nums:
       for y in nums[:x]:
           output.append(x + y)
    return output

Solution using chained generator expression

def twosum_indices(nums, target):
    return next((i, j) for i in range(len(nums)) for j in range(len(nums[:i])) if (nums[i] + nums[j] == target))

Examples:

print(sorted(twosum_indices([2, 7, 11, 15], 9)))
[0, 1]

print(sorted(twosum_indices([3, 3], 6)))
[0, 1]

Solution using generator expression with itertools

It's a tad simpler with itertools:

import itertools

def twosum_indices_it(nums, target):
    return next((i, j) for (i, x), (j, y) in itertools.combinations(enumerate(nums), 2) if (x + y == target))

Examples:

print(sorted(twosum_indices_it([2, 7, 11, 15], 9)))
[0, 1]

print(sorted(twosum_indices_it([3, 3], 6)))
[0, 1]

Answer 2

#! /usr/bin/env python3


def two_sum_indices(nums, target):

    def dup(i, j):
        return i == j

    d = {num: i
         for i, num in enumerate(nums)}

    for i, num in enumerate(nums):
        if target - num in d:
            if not dup(i, d[target - num]):
                return i, d[target - num]
    return -1, -1


if __name__ == '__main__':

    print(two_sum_indices([2, 7, 11, 15], target=9))
    print(two_sum_indices([3], target=6))
    print(two_sum_indices([3, 3], target=6))