知识卡片
两数和先查补数再存当前
扫描到值x时,在已经见过的元素映射里查询target-x;若存在,就用旧索引和当前索引组成答案,否则再记录当前值及位置。这样避免把同一个元素使用两次。
空间换掉内层线性查找,哈希条件满足时得到期望线性时间、线性额外空间。整数加减仍要在声明范围内,题目是否允许多个答案或重复值也要明确,不能把此解称为不带任何条件的唯一最优。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
将键值对nums[i] 和索引i 添加进哈希表。 第10 章 搜索 hello‑algo.com 222 图10‑10 辅助哈希表求解两数之和 实现代码如下所示,仅需单层循环即可: // === File: two_su
参考来源
- 位置:《Hello 算法--Go版本》第10章《搜索》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[16277,16387))
- 结论依据:实际twoSum先查后存代码,突出顺序与索引不同的原因。
- 原始内容:将键值对nums[i] 和索引i 添加进哈希表。 第10 章 搜索 hello‑algo.com 222 图10‑10 辅助哈希表求解两数之和 实现代码如下所示,仅需单层循环即可: // === File: two_su