0170. Two Sum III - Data structure design ========================================= 题目信息 -------- :题号: 0170. 两数之和 III - 数据结构设计 :难度: Easy :主题: 数据结构设计、哈希表、补数查询 :原题: `LeetCode 0170 `_ :重点: 在多次 add/find 操作间分配工作,用频次而非存在性处理两个相同加数 题目重述 -------- 设计 ``TwoSum`` 数据结构,支持两种操作: * ``add(number)``:把整数 ``number`` 加入数据结构;同一个值可以加入多次; * ``find(value)``:判断当前已加入的数中,是否存在两个不同的加入记录,其和等于 ``value``。 ``find`` 只返回是否存在,不需要返回下标或删除元素。若答案使用两个相同数值,该数值 必须至少被加入两次。 自建示例 -------- .. code-block:: text TwoSum two_sum; two_sum.add(1); two_sum.add(3); two_sum.add(5); two_sum.find(4); // true,1 + 3 = 4 two_sum.find(7); // false two_sum.add(3); two_sum.find(6); // true,两个独立加入的 3 .. code-block:: text TwoSum two_sum; two_sum.add(-4); two_sum.add(10); two_sum.find(6); // true,-4 + 10 = 6 two_sum.find(-8); // false,-4 只加入了一次 C++ 实现 -------- .. code-block:: cpp #include class TwoSum { private: std::unordered_map frequency_; public: TwoSum() = default; void add(int number) { ++frequency_[number]; } bool find(int value) { for (const auto& [number, count] : frequency_) { long long complement = static_cast(value) - number; auto found = frequency_.find(complement); if (found == frequency_.end()) { continue; } if (complement != number || count >= 2) { return true; } } return false; } }; 题解 ---- 从一次性问题到操作序列 ~~~~~~~~~~~~~~~~~~~~~~ 一次性“两数之和”可以扫描数组并维护已见补数;本题没有固定数组,而是让 ``add`` 与 ``find`` 任意交错。每次 ``find`` 都重新枚举全部加入记录的数对当然正确,但若已经加入 ``n`` 个数,一次查询就可能检查 ``O(n²)`` 对。多次查询还会重复验证完全相同的数对。 数据结构设计的核心不是寻找另一个公式,而是决定哪些工作在 ``add`` 时完成、哪些留给 ``find``: * 保存全部数值列表:``add`` 为 ``O(1)``;``find`` 可以临时建立已见集合,用一次扫描 查补数,时间 ``O(n)``,但每次查询都会重新处理重复值; * 保存数值频次:``add`` 期望 ``O(1)``;``find`` 只扫描 ``u`` 个不同值,空间 ``O(u)``,其中 ``u`` 是不同值数量; * 预先保存所有可形成的两数之和:每次加入新数时与已有不同值组合,``add`` 为 ``O(u)``、空间最坏 ``O(u²)``,但 ``find`` 可变成一次期望 ``O(1)`` 查询。 主解采用频次表:它没有二次空间,在 ``add`` 和 ``find`` 之间保持较均衡的代价;大量 重复输入还会被压缩成一个键和一个计数。 补数查询与重复值陷阱 ~~~~~~~~~~~~~~~~~~~~ 扫描某个已加入值 ``number`` 时,另一个数必须是: .. code-block:: text complement = value - number 若补数与 ``number`` 不同,频次表中存在该键就说明有两种不同数值,它们自然对应两条 加入记录。若两者相同,键存在只说明至少加入过一次;必须要求 ``count >= 2``,才能使用 两个不同记录。 这正是集合无法完整表达的地方。集合能回答“3 是否出现过”,却无法区分一次还是两次, 因而会把只加入一个 3 的 ``find(6)`` 误判为真。频次是本题相对于普通存在性查询必须保留 的新信息。 状态走读 ~~~~~~~~ 执行示例中的前五个操作后,状态为: .. code-block:: text frequency = {1: 1, 3: 1, 5: 1} ``find(4)`` 扫描到 1 时计算补数 3,两个键不同且 3 存在,立即返回真。 ``find(7)`` 的候选补数依次为 6、4、2,都不存在,所以返回假。 再次执行 ``add(3)`` 后,只有已有键的计数从 1 变成 2: .. code-block:: text frequency = {1: 1, 3: 2, 5: 1} 此时 ``find(6)`` 扫描到 3,补数仍为 3;相同键分支检查计数 2,确认存在两条独立记录后 返回真。``find`` 不修改频次,因此任意次数的查询都不会消耗数据。 为何不需要去重数对 ~~~~~~~~~~~~~~~~~~ 扫描 1 时可能检查 ``1 + 3``,以后扫描 3 又可能检查 ``3 + 1``。这会让某些失败查询 做常数倍重复工作,但不会影响 ``O(u)`` 复杂度;成功查询在第一次命中时立即返回。 若强行只检查 ``number <= complement`` 可以减少重复,却会增加边界分支,且无法改变 渐近复杂度。主解保持“每个不同值查询一次补数”的直接不变量,代码与正确性更清晰。 数值边界与复杂度 ~~~~~~~~~~~~~~~~ ``value - number`` 在 32 位整数上可能溢出,所以哈希键和补数计算使用 ``long long``。 加入的输入仍由题目接口提供 ``int``,提升后不会改变其值;超出输入范围的补数只会自然 查询失败。 设当前有 ``u`` 个不同值。``add`` 的期望时间为 ``O(1)``;``find`` 扫描频次表,期望 时间为 ``O(u)``;空间为 ``O(u)``。这些是哈希表平均情况下的复杂度,极端冲突下的最坏 时间取决于具体容器实现。若使用场景中查询远多于加入,并能接受二次空间,才值得改用 预计算所有两数之和的设计。