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 会把下标打乱(得额外带下标排序),所以哈希表一遍扫更顺手。
图解
数组(来自本仓库测试数据,下标从 0 开始)
扫描到
nums[1]=7,查 seen[9-7=2] 命中 下标0,返回 [0,1]。先查后存,避免自配对。逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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 {}; // 题目保证有解,这里只是编译器安心
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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});