Two Sum on LeetCode

Question

I'm trying to do a LeetCode question:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

The first try was using two for loops, which gave me O(n^2), and unfortunately it didn't pass. Hence I tried to use:

target - current = index

And search for if the index does exists on a dictionary.

This is my code:

class Solution:
    def twoSum(self, nums, target):
        dic = {}

        #A number can appear twice inside the same index, so I use a list
        for i in xrange(0, len(nums)):
            try:
                dic[nums[i]].append(i)
            except:
                dic[nums[i]] = []
                dic[nums[i]].append(i)

        try:
            for items_1 in dic[nums[i]]:
                for items_2 in dic[target-nums[i]]:
                    if(items_1+1 != items_2+1):
                        l = []
                        if(items_2+1 > items_1+1):
                            l.append(items_1+1)
                            l.append(items_2+1)
                        else:
                            l.append(items_2+1)
                            l.append(items_1+1)
                        return l
        except:
            pass

I developed this locally, and I was able get the correct result with one of the test case that LeetCode was complaining: [-3,4,3,90], 0

The output I got was [1, 3], but on LeetCode it returned null, does anybody know why this would happen?

Answer 1

I have just passed the following codes. To take advantage the dictionary and the notes that there is one and only one solution. To search the target-num in the saved lookup dictionary when saving the num in the lookup dictionary one by one. This method could save the space and also prevent the index overwriting when there are two same values in the nums.

def twosum(self, nums, target):
    lookup = {}
    for cnt, num in enumerate(nums):
        if target - num in lookup:
            return lookup[target-num], cnt
        lookup[num] = cnt            

Answer 2

this is my answer

class Solution:
    def twoSum(self, nums, target):
        ls = []
        for i in range(0, len(nums)):
            item = target - nums[i]
            nums[i] = "done"
            if item in nums:
                ls.append(i)
                ls.append(nums.index(item))
                return ls

Answer 3

You want something along these lines:

#! python3

def two_sum(arr,targ):
    look_for = {}
    for n,x in enumerate(arr,1):
        try:
            return look_for[x], n
        except KeyError:
            look_for.setdefault(targ - x,n)

a = (2,7,1,15)
t = 9
print(two_sum(a,t))  # (1,2)

a = (-3,4,3,90)
t = 0
print(two_sum(a,t))  # (1,3)

Here you build the dictionary of values on an as-needed basis. The dictionary is keyed by the values you are seeking, and for each value you track the index of its first appearance. As soon as you come to a value that satisfies the problem, you're done. There is only one for loop.

The only other detail is to add 1 to each index to satisfy the ridiculous requirement that the indices be 1-based. Like that's going to teach you about Python programming.

Keys are added to the dictionary using the setdefault function, since if the key is already present you want to keep its value (the lowest index).

Answer 4

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        r = []

        for i in range(len(nums)):
            temp = target - nums[i]
            if temp in r:
                return [i,nums.index(temp)]

            r.append(nums[i])

Answer 5

I like

    def two_sum(arr,targ):
        look_for = {}
        for n,x in enumerate(arr,1):
            try:
               return look_for[x], n
            except KeyError:
               look_for.setdefault(targ - x,n)

above but it fails timedome due to call to enumerate taking too long for large arrays. Better to skip the enumerate and just keep a count of index:

def findCombo(l,target):
    lookup = {}
    n = 0
    for x in l:
        try:
            return (n,lookup[x])
        except KeyError:            
            lookup.setdefault (target-x,n)
        n = n + 1

    return None

Note:Python timedome question uses index starting at 0

Answer 6

This answer uses zero-based indexing since that's the normal way to index, not one-based indexing. It also uses descriptive variable names. It is written for comprehension.

def twosum_indices_linear(nums, target):
    numtoindexmap = {}
    for num1_index, num1 in enumerate(nums):
        num2 = target - num1
        try:
            num2_index = numtoindexmap[num2]
        except KeyError:
            numtoindexmap[num1] = num1_index
        else:
            return num1_index, num2_index

Examples:

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

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

print(sorted(twosum_indices_linear([6, 7, 11, 15, 3, 6, 5, 3], 6)))
[4, 7]

Credit: answer by joeg