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

def twoSum(nums,target):
    k={value:index for index, value in enumerate(nums)} 
    # using dictionary comprehesion to create a dictionary that maps value to index 
    ans=[[j,k[target-x]] for j,x in enumerate(nums) if target-x in k] 
    # use list comprehension to create a set of answers; make sure no key error by using 'if target-x in k'
    ans=[x for x in ans if x[0] != x[1]] 
    # make sure the two indexes are not the same. E.g. twoSum([1,2,0],2) returns [[0,0],[0,1],[1,2],[2,1]]; and [0,0] is a wrong answer  
    return ans[0]

This solution is time efficient (faster than 80% of the solutions on leetcode), but takes lots memory.

Answer 2

def twosum(nums=(6, 7, 11, 15, 3, 6, 5, 3), target=6):
    lookup = dict(((v, i) for i, v in enumerate(nums)))
    return next(( (i+1, lookup.get(target-v)+1) 
            for i, v in enumerate(nums) 
                if lookup.get(target-v, i) != i), None)

I have not tested this extensively but the basic logic should be sound. This algorithm can be broken up into two stages:

1. Create a dictionary of value->index for all index, value pairs in nums. Note that you can have multiple values with different indices. In this case, the highest index will be stored in the dictionary and lower indexes will be overwritten. This behavior can be modified, of course, but I don't believe it needs to be for this problem because part of the problem statement is this: "You may assume that each input would have exactly one solution." Thus, each input has a single unique output so we never have to worry about returning a "wrong-pair" of indices.

2. Loop through the enumeration of nums, getting i as index, and v as value. Check if target-v is a key in the dictionary we created, and simultaneously assert that the value pointed to by that key is not i. If this is ever true, return the tuple i+1, lookup.get(target-v)+1.