LeetCode Hot 100：两数之和
用哈希表把 Two Sum 的查找降到 O(1)，看清补数查找为什么要先查后存。
两数之和：用哈希表把查找降到 O(1)
这期讲 LeetCode Hot 100 的 Two Sum。题目要求在整数数组中找到两个数，使它们相加等于 target，并返回这两个数的下标；每个输入只有一个答案，同一个元素不能使用两次。
视频里的核心方法是：扫描数组时，用
Map 记录已经见过的数字和下标。每次先计算当前数字需要的补数，再去表里查；命中就返回答案，没命中才把当前数字写入表。这样可以把暴力枚举的两层循环，改成一次线性扫描。function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (seen.has(need)) {
return [seen.get(need), i];
}
seen.set(nums[i], i);
}
}来源
관련 콘텐츠
- 로그인하면 댓글을 작성할 수 있습니다.