2018-06-02 1 Two Sum

1. O(nlogn)

First sort the list. Then use two pointers from beginning and end to search.
'''

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    sorted_nums = nums[:]
    sorted_nums.sort()
    len_list = len(nums)
    
    i = 0
    j = len_list - 1
    num_1 = sorted_nums[i]
    num_2 = sorted_nums[j]
    while sorted_nums[i] + sorted_nums[j] != target:
        if sorted_nums[i] + sorted_nums[j] > target:
            j -= 1
        elif sorted_nums[i] + sorted_nums[j] < target:
            i += 1
        num_1 = sorted_nums[i]
        num_2 = sorted_nums[j]
        
    num_1_idx = nums.index(num_1)
    if num_1 == num_2:
        num_2_idx = nums.index(num_2, num_1_idx+1)
    else:
        num_2_idx = nums.index(num_2)
    
    return [num_1_idx, num_2_idx]

'''

2. O(n)

Use dictionary to store the value2index. Iterate once.
'''

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    num2idx_dict = {}
    len_list = len(nums)
    for i in xrange(len_list):
        complement = target - nums[i]
        if complement in num2idx_dict:
            return [num2idx_dict[complement], i]
        num2idx_dict[nums[i]] = i

'''