题目链接:https://leetcode.com/problems/two-sum/

题目大意:在整形数组 nums 中找到两个数字,使得两数之和等于 target,返回这两个数的索引。

题目限制:

  • 数组长度 $[2, 10^5]$
  • 数组值范围 $[-10^9, 10^9]$
  • 目标值范围 $[-10^9, 10^9]$
  • 保证有且只有唯一解存在

思路一:Brute-Force

暴力解法即直接对数组 nums 进行双重遍历,找到 nums[i] + nums[j] == target 后返回 ij .

时间复杂度:$O(n^2)$ – 双层 for 循环遍历数组,在数据规模较大时必然导致 Time Limit Exceeded (TLE)

空间复杂度:$O(1)$

思路二:Hash Table (Two-pass)

根据“用空间换时间”的思想进行优化,在思路一中等同于在内层循环中查找 nums[j] == target - nums[i], 这一步的时间复杂度为 $O(n)$,可以通过使用哈希表(Hash Table)使得查询操作的时间复杂度优化到 $O(1)$.

  1. 在第一次遍历数组时,形成这样一个 Key-Value 数据结构,其中 Key 存储当前的数值 nums[i],Value 中存储当前值在数组中的索引位置 i
  2. 在第二次遍历数组时,寻找 left = target - nums[i] 这个 Key 是否存在于数据结构中,找到了则直接返回 iindices[left] .

注意事项:

  • 需要加上 indices[left] != i 防止找到的索引和当前相同;
  • C++ 中 STL 容器的 count()find() 函数都可使用, find() 效率会更高些;

时间复杂度:$O(n)$ – 使用哈希表将 $O(n)$ 的查询成本优化到了 $O(1)$.

空间复杂度:$O(n)$ – 哈希表元素的存储带来了额外的空间开销。

思路三:Hash Table (One-pass)

思路二的解法需要遍历两遍 nums 数组,我们可以优化为一次遍历,方法是在生成哈希表的同时进行查询操作。虽然分析得到的时间复杂度没有降低,但是通过减少遍历次数和提前 return 的形式达到了进一步优化的效果。

注意事项:

  • 这里使用了 find(), 和思路二 count() 效果一致,但底层效率会更快些;
  • 这个写法同时也避免了思路二中对索引相同时的额外判断;
  • 题目对返回的索引没有做顺序要求,如果有要求则需要注意。

时间复杂度:$O(n)$ – 理论上比思路二更优。

空间复杂度:$O(n)$ – 理论上比思路二更优。