two sum python solution

class Solution:
def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    for i in nums:
        j=target-i 
        if ((j in nums)==True and (nums.index(j) != nums.index(i))):
            return [nums.index(i), nums.index(j)]

it passed the case for list [2,7,11,15] but not [3,3]. I am not sure what the issue is.


This works and can do it in a single pass:

from collections import defaultdict

# Returns the indices of two numbers that add up to the target
def two_sums(nums, target):

    lookup = defaultdict(list)
    for i, num in enumerate(nums):
        needed = target - num
        if needed in lookup:
            return [lookup[needed][0], i]
        lookup[num].append(i)

    return None

print(two_sums([2,7,11,15], 17))
print(two_sums([3, 3], 6))

Another solution might be:

def two_sum(nums, target):
    d = {}
    for i in range(len(nums)):
        x = nums[i]
        if target - x in dict:
            return (d[target - x] + 1, i + 1)
        d[x] = i
    return None

I found 3 main ways to solve this question, the 1st approach is brute force with time complexity of O(n^2) and space complexity of O(1):

def twoNumberSum(array, targetSum):
    for i in range(0, len(array)):
        for j in range(i+1, len(array)):
            if array[i] + array[j] == targetSum:
                return ([array[i], array[j]])
    return []

The 2nd approach is using hash map with time complexity of O(n) and space complexity of O(n):

def twoNumberSum(array, targetSum):
    matches = {}
    for number in array:
        match = targetSum - number
        if match in matches:
            return [match, number]
        else:
            matches[number] = True
    return []

The 3rd approach is with two pointers of left and right. This method has time complexity of O(nlogn) and space complexity of O(1):

def twoNumberSum(array, targetSum):
    array.sort()
    left = 0
    right = len(array) - 1
    while left < right:
        if array[left] + array[right] == targetSum:
            return [array[left], array[right]]
        elif array[left] + array[right] < targetSum:
            left +=1
        elif array[left] + array[right] > targetSum:
            right -=1
    return []