LeetCode刷题 1 两数之和

题目

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例

给定 nums = [2, 7, 11, 15]，target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回[0, 1]

思考

最简单、最直接的想法就是暴力的嵌套的双循环，遍历每个元素计算。空间复杂度虽然是O(1)，但是时间复杂度却是O()，因为对于每个元素，都试图遍历它以外的所有元素来求解，这一次循环就耗费O(n)时间。所以对于长度越长的数组来说效率越低。
所以需要一种更有效的方法来检查数组中是否存在所需的元素。如果存在，就返回它的索引。这里可以使用哈希表。通过牺牲空间换取时间。可以将查找时间从O(n)降底到O(1)，哈希表正是为此目的而构建，它支持以近似恒定的时间进行快速查找。之所以“近似”，是因为一旦出现冲突，查找时间可能退化到O(n)。只要仔细的挑选哈希函数，在哈希表中进行查找的用时应当被摊销为O(1)。
使用哈希表的话，时间复杂度为O(n)，因为查找时间缩短到了O(1)。空间复杂度为O(n)。

解题思路

关键点在于 nums[i] + nums[j] = target，即等于 nums[i] = target - nums[j]。可以做个哈希表，表里面存储以target - nums[j](目标元素)为键，当前索引为值。在迭代并将元素插入到表中的同时，进行检查表中是否已经存在当前元素所对应的目标元素。如果存在，即找到对应解，立即返回。

Python实现

Python里面的字典就是利用哈希表存储的，可以拿来直接使用。

class Solution:
  def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    if len(nums) <= 1:
      return [0, 0]

    d = dict()
    for i in range(len(nums)):
      if nums[i] in d:
        return [d[nums[i]], i]
      else:
        d[target - nums[i]] = i

在LeetCode上跑了44ms

C++实现

C++的话，需要使用里面的hash_map，std里面还有map，map底层是使用红黑树存储的。查找时间复杂度是O()。
有关hash_map的介绍可以阅览《详细解说STL hash_map系列》。那么正常情况下什么时候用map，什么时候用hash_map？需要具体看应用，复杂度为常数级别O(1)的hash_map就一定比O()级别的map要好，hash_map的hash函数以及解决地址冲突等都需要耗时，而且hash表是以空间效率来换取时间效率的，所以hash_map所耗内存更大。一般情况下，数据量很大的时候，可以考虑使用hash_map，可以提高查找效率。但如果需要谨慎使用内存的时候，就应该考虑使用map了。
(2018/07/09追加，根据C++ 11标准的推荐，用unordered_map代替hash_map。关于unordered_map可以参考下面文章的介绍)

class Solution
{
  public:
    std::vector<int> twoSum(std::vector<int>& nums, int target)
    {
      std::unordered_map<int, int> dict;
      std::vector<int> result;
      for(int i = 0; i < nums.size(); ++i)
      {
        auto it = dict.find(nums[i]);
        if(it != dict.end())
        {
          result.push_back(dict[nums[i]]);
          result.push_back(i);
          return result;
        }
        else
        {
          dict.insert(std::pair<int, int>(target - nums[i], i));
        }
      }
      return result;
    }
};

在LeetCode上跑了8ms