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.

Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i!=j:
                    if nums[i] + nums[j] == target:
                        return [i, j]


nums = [2, 7, 11, 15]
target = 9
sol = Solution()
print sol.twoSum(nums, target)

This is simple since you can look through each element in the array and compare their sum with the target number. But, the complexity of this solution is O(n^2), since you are going through the list once every element in the list.

What about this?

class Solution(object):
    def twoSum(self, nums, target):
        dict = {}
        for i in range(len(nums)):
            if dict.has_key(target-nums[i]):
                return (dict[target-nums[i]][1], i)
            else:
                dict.setdefault(nums[i], (target-nums[i], i))

nums = [2, 7, 11, 15]
target = 9
sol = Solution()
print sol.twoSum(nums, target)

This is a lot simpler in terms of complexity. The pointer goes through the array once, picking out each element and seeing what number needs to be paired with it to sum up to the target number.
Then, we put that in a dictionary. For example, element in index 0 would be stored as a key and it's leftover and index as a tuple for a value dict[2]:(7, 0).

Every time we look at an element we figure out if we have a corresponding number already in the dictionary, and if we do, then we return the index stored as well as the index we are currently on.
This make for an O(n) complexity.