HHot 100C++ 图解

1. 两数之和

一句话套路哈希存「值→下标」,查 target-x

题目描述

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

你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示:

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

 

进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?

思路

时间O(n)
空间O(n)

思路

一次遍历,哈希表里存「已经看过的值 -> 下标」。

对当前 nums[i],先查 target-nums[i] 在不在表里,再把自己塞进去。

顺序「先查后存」保证不会用同一个元素两次([3,3] target=6 也能过)。

对比

暴力二重循环 O(n^2);本题要返回下标,直接 sort 会把下标打乱(得额外带下标排序),所以哈希表一遍扫更顺手。

图解

2 0 7 1 11 2 15 3
数组(来自本仓库测试数据,下标从 0 开始)
2 0 7 1 11 2 15 3 l r
扫描到 nums[1]=7,查 seen[9-7=2] 命中 下标0,返回 [0,1]。先查后存,避免自配对。

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/01_hash.cpp15 行
namespace lc0001 {
class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // 值 -> 下标
    seen.reserve(nums.size() * 2);
    for (int i = 0; i < (int)nums.size(); ++i) {
      auto it = seen.find(target - nums[i]);
      if (it != seen.end()) return {it->second, i};
      seen[nums[i]] = i;
    }
    return {};  // 题目保证有解,这里只是编译器安心
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q1_two_sum9 行
lc0001::Solution s;
vector<int> a{2, 7, 11, 15};
CHECK_EQ(s.twoSum(a, 9), vector<int>{0, 1});
vector<int> b{3, 2, 4};
CHECK_EQ(s.twoSum(b, 6), vector<int>{1, 2});
vector<int> c{3, 3};  // 重复元素:先查后存才不会自配
CHECK_EQ(s.twoSum(c, 6), vector<int>{0, 1});
vector<int> d{2, 5, 5, 11};
CHECK_EQ(s.twoSum(d, 10), vector<int>{1, 2});

↑↓ 选择↵ 打开/ 随时唤起