0. 原理

具体可以参考我的另一篇文章。

1. 两数之和(leetcode_1)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例： 给定 nums = [2, 7, 11, 15], target = 9> 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

此题有三种解法：

  1. 暴力法

时间复杂度哈希表 - 图1；空间复杂度哈希表 - 图2

  1. 两遍哈希表法

时间复杂度哈希表 - 图3；空间复杂度哈希表 - 图4

  1. 一遍哈希表法

时间复杂度哈希表 - 图5；空间复杂度哈希表 - 图6

1.1 暴力解法

时间复杂度哈希表 - 图7；空间复杂度哈希表 - 图8

  1. class Solution(object):
  2.     def twoSum(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: List[int]
  7.         """ 
  8.         length = len(nums)
  9.         for first_index in range(length-1):
  10.             for second_index in range(first_index+1, length):
  11.                 if nums[first_index] + nums[second_index] == target:
  12.                     return [first_index, second_index]
  13.         else:
  14.             return -1

1.2 两遍哈希表

即空间换时间的思想。时间复杂度哈希表 - 图9；空间复杂度哈希表 - 图10。

  1. class Solution(object):
  2.     def twoSum(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: List[int]
  7.         """ 
  8.         dict_ = {}
  9.         for index, val in enumerate(nums):
  10.             dict_[val] = index
  11.         for index, val in enumerate(nums):
  12.             if target - val in dict_.keys():
  13.                 if index != dict_[target-val]:
  14.                     return [index, dict_[target-val]]
  15.         return -1

1.3 一遍哈希表法

即有点类似于动态规划搜索，一边遍历一边存储一边查找的思想。时间复杂度哈希表 - 图11；空间复杂度哈希表 - 图12。

  1. class Solution(object):
  2.     def twoSum(self, nums, target):
  3.         """
  4.         :type nums: List[int]
  5.         :type target: int
  6.         :rtype: List[int]
  7.         """ 
  8.         dict_ = {}
  9.         for index, val in enumerate(nums):
  10.             if target - val in dict_.keys():
  11.                 return [index, dict[target-val]]
  12.                else:
  13.                 dict_[val] = index
  14.         return -1

这里需要注意两点：

  1. 哈希表的hashMap.containsKey()平均复杂度为哈希表 - 图13，最坏状况为哈希表 - 图14，实际中看做哈希表 - 图15即可。
  2. 虽然一遍哈希和两遍哈希时间和空间复杂度表面上一样，但是实际运行中，一遍哈希还是比两遍哈希更快的，因为实际情况中需要完全遍历到列表末尾的概率很小，但是他们的整体复杂度是相同的，这一知识点具体可以参考我的另一篇关于复杂度哈希表 - 图16的文章。
  3. 暴力法和哈希法各有各的优劣，并没有绝对的好与坏之分，应该具体情况具体分析。比如
    1. 当我们空间足够大需要时间尽可能短，即算法相应尽可能快的话，当然哈希法更好；
    2. 当列表中的数字非常多，我们的空间内存不足，并且并不太在意时耗时，当然暴力法更好。