【LeetCode】#1 Two Sum

【Question】

  • 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].


【My Solution】

  • Brute Force
class Solution(object):
    def twoSum_update(self, nums ,target):
        """
        Brute Force: Loop through each element x 
        find if there is another value that equals to target - x
        """
        l = len(nums)
        for i in range(l):
            for j in range(i+1, l):
                if (nums[i] == target - nums[j]):
                    return [i,j]
        raise ValueError("No two sum solution")
  • 分析
    双重循环遍历查询满足条件的数值

  • Complexity Analyze:

  1. Time complexity : \(O(n^2)\). For each element, we try to find its complement by looping through the rest of array which takes \(O(n)\) time. Therefore, the time complexity is \(O(n^2)\). 容易出现TLE

  2. Space complexity : \(O(1)\).


【Other Solution #1】

  • Two-pass Hash Table 两段式哈希表
class Solution(object):
    def twoSum(self, nums ,target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = len(nums)
        hash = {}
        for i in range(l):
            hash[nums[i]] = i 
        for i in range(l):
            if target-nums[i] in hash and hash[target-nums[i]]!=i:
                return [i, hash[target-nums[i]]]
        raise ValueError("No two sum solution")
  • 分析
    利用Python中的dict来进行对求差所得的数值的查找。由于dict采用哈希结构,查找所需时间接近 \(O(1)\) (在发生冲突时可能会退化到 \(O(n)\) ),通过空间换取时间。最简单的实现方式是采用两轮循环,第一轮将每个元素及其索引添加进哈希表,第二轮检查当前元素对于target的补数是否在这个表中,另外要注意的是该补数不能是当前元素。

  • Complexity Analyze:
  1. Time complexity : \(O(n)\). We traverse the list containing n elements exactly twice. Since the hash table reduces the look up time to \(O(1)\), the time complexity is \(O(n)\).

  2. Space complexity : \(O(n)\). The extra space required depends on the number of items stored in the hash table, which stores exactly n elements.


【Other Solution #2】

  • One-pass Hash Table 一段式哈希表
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = len(nums)
        hash_map = {}
        for i in range(l):
            if target-nums[i] in hash_map:
                return [hash_map[target-nums[i]], i]
            hash_map[nums[i]] = i
        raise ValueError("No two sum solution")
  • 分析
    基于上面的两段式哈希表,可以改进成一段式哈希表,在循环遍历元素的时候进行哈希表的插入,并且可以同时回头查询当前元素的补数是否也存在于表中,存在的话可以立即返回。

  • Complexity Analysis:

  1. Time complexity : \(O(n)\). We traverse the list containing nn elements only once. Each look up in the table costs only \(O(1)\) time. 虽然同样是 \(O(n)\),但比此前的方案少了一半的常数项。

  2. Space complexity : \(O(n)\). The extra space required depends on the number of items stored in the hash table, which stores at most n elements. 空间上也比此前方案有了一定的优化,有时并不需要完全遍历一遍元素。