1. 两数之和

（1）题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 O(n²) 的算法吗？

（2）题解

  • 暴力法 O(n²)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for (int i = 0; i < nums.size() - 1; ++i)
    {
      for (int j = i + 1; j < nums.size(); ++j)
      {
        if (nums[i] + nums[j] == target)
        {
          return {i, j};
        }
      }
    }

  • 哈希表 O(n)

    将每一个元素作为 key ，将其索引值作为 value 。每次查询一个元素，并与 target 做差（ target - key），如果差在表中可查，则找到并输出当前元素和查到的元素的 value ；否则检查下一个元素。

    LeetCode-1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 构建哈希表
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); ++i){
      map.emplace(nums[i], i);
    }

    # 逐一检查
    for (int j = 0; j < nums.size(); ++j){
      int diff = target - nums[j];
      if (map.find(diff) != map.end() and map[diff] != j){
        return {j, map[diff]};
      }
    }

  • 哈希表进一步改进

    先查询 target - nums[i] 值是否存在，如果不存在才将 nums[i] 插入哈希表，等待后面的数字做差后与之比较；如果存在，则说明找到了，不必再验证后续的值，直接输出即可。

    该方法可以减少省去构建哈希表时的循环，时间复杂度相同，但可节省内存空间的占用。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    unordered_map<int, int> hashtable;

    for (int i = 0; i < nums.size(); ++i) {
      auto it = hashtable.find(target - nums[i]);
      if (it != hashtable.end()) {
        return {it->second, i}; //有则输出
      }
      hashtable[nums[i]] = i; //无则插入
    }

（3）知识点