1.Two Sum

Tags: [map], [sort], [two_pointer]

Com: {fb}

Link: https://leetcode.com/problems/two-sum/#/description

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, and you may not use the same element twice.

Example:

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

Solution: Map

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums) < 2:
            return []

        num_map = {}
        for i in xrange(len(nums)):
            curr = nums[i]
            if curr not in num_map:
                num_map[curr] = i

            if (target - curr in num_map) and (num_map[target - curr] != i):
                return [num_map[target - curr], i]

        return []

Note:

• The requirement is that cannot use the same element two times, so we check 'num_map[target - curr] != i'.
• Time complexity = O(n), n is the number of elements of the given nums.
• Space complexity = O(n), n is the number of elements of the given nums.

Solution: Sort, Two Pointers

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums) < 2:
            return []

        arr = []
        for i in xrange(len(nums)):
            arr.append((nums[i], i))

        arr.sort(key=lambda x: x[0])

        left = 0
        right = len(arr) - 1
        while left < right:
            curr_sum = arr[left][0] + arr[right][0]
            if curr_sum == target:
                return [arr[left][1], arr[right][1]]
            elif curr_sum < target:
                left += 1
            else:
                right -= 1

        return []

Revelation:

• Need to record the original index.

Note:

• Time complexity = O(nlgn), n is the number of elements of the given nums.
• Space complexity = O(n), n is the number of elements of the given nums.