知识卡片

普通读书笔记卡 · 5654.d.1.a.3.c

两数和先查补数再存当前

理解等级:中级

扫描到值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