LeetCode刷题-1-两数之和

给定一个 整数数组 和一个 目标值 ，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例

给定 nums = [2, 7, 11, 15]，target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]

最简单、最直接的想法就是暴力的嵌套的双循环，遍历每个元素计算。空间复杂度虽然是 O(1)，但是时间复杂度却是 O($n^2$)，因为对于每个元素，都试图遍历它以外的所有元素来求解，这一次循环就耗费 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 里面的字典就是利用哈希表存储的，可以拿来直接使用。

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++ 的话，需要使用里面的 hash_map，std 里面还有 map，map 底层是使用红黑树存储的。查找时间复杂度是 O($logn$)。
有关 hash_map 的介绍可以阅览《详细解说 STL hash_map 系列》。那么正常情况下什么时候用 map，什么时候用 hash_map？需要具体看应用，复杂度为常数级别 O(1)的 hash_map 就一定比 O($logn$)级别的 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

LeetCode刷题-1-两数之和

题目

思考

解题思路

Python 实现

C++ 实现