LeetCode 170. 两数之和 III - 数据结构设计

2023-04-20 HGNULB 约 9 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 170. 两数之和 III - 数据结构设计

题意分析

要设计一个支持两种操作的容器：add(number) 往里塞一个整数，find(value) 回答「容器里是否存在两个不同位置的元素，它们的和恰好等于 value」。

「两个不同位置」这五个字是全题的关键。它不要求两个数的值不同，只要求它们是两次不同的 add 塞进来的。所以当 value 恰好是某个数的两倍时，必须确认这个数至少被添加过两次——只出现一次的话，它不能和自己配对。这是本题唯一的语义陷阱，也是它与 1 题最本质的差别。

与 1 题的第二个差别是：这里没有一次性给定的数组，而是在线的操作流。数据随时会追加，查询随时会到来，无法在某个时刻做一次性的全量预处理。设计题的评价标准也因此从「总复杂度」变成了「每个操作各自的复杂度」，以及两者之间的取舍。

题面没有承诺 add 与 find 的调用比例，也没有承诺数值范围很小，所以设计时要在心里先假设「两种操作都可能很频繁」，再决定把成本压在哪一边。

边界包括：容器为空时调用 find；只加了一个元素时查询它的两倍；重复添加同一个数；以及 value 恰好等于某个元素的两倍但该元素只有一份。

解法：哈希表维护状态映射

核心思路

最朴素的实现是用一个列表保存所有添加过的数，find 时双重循环枚举所有下标对。add 是 $O(1)$，但 find 是 $O(n^2)$，查询稍多就撑不住。瓶颈在于「找配对」被当成了盲目枚举，而配对关系其实是确定的：给定 value 和其中一个数 x，另一个数只能是 value - x，没有第二种可能。

于是问题从「枚举两个数」降为「枚举一个数，再查另一个在不在」。这一步把 $O(n^2)$ 压成了 $O(n)$ 乘以单次查找的成本，而哈希表让单次查找是均摊 $O(1)$。

但只用「是否存在」的集合还不够，因为要处理自我配对。集合无法区分「这个数出现过一次」和「出现过多次」，而这两种情况在 value = 2x 时结论完全相反。所以容器选哈希计数表：键是数值，值是它被添加的次数。

不变量是：计数表在任意时刻都精确记录了「每个数值被 add 过多少次」。add 只做一次自增，保证不变量维持；find 只读不写，不破坏不变量。

find(value) 的逻辑是遍历计数表的每个键 x，令 y = value - x：若 y != x，只需检查 y 是否作为键存在——两个不同的数值必然来自两次不同的添加；若 y == x，则必须检查 x 的计数是否达到 2，否则就是「拿自己和自己凑」的非法配对。找到任何一组即可返回真，遍历完都没找到则返回假。

遍历的是键的集合而不是所有添加过的元素，所以 find 的成本与不同数值的个数成正比，而不是与总添加次数成正比。重复添加同一个数不会拖慢查询，这是选计数表而非列表的额外收益。

解题步骤

构造函数里初始化一张空的哈希计数表。键为数值、值为出现次数。用计数而不是布尔标记，是为了让自我配对可判定；这个决定必须在设计之初就做出，事后补救要改动所有接口。

add(number) 把对应计数加一。取不到就当作 0 再加一。这是唯一的写入路径，保证计数表始终与添加历史一致。整个操作是均摊 $O(1)$，把成本全部留给了查询侧。

find(value) 遍历计数表的所有键。对每个键 x 算出配对值 y = value - x。这里遍历键而不是遍历原始序列，避免了重复元素带来的无谓重复检查。

分两种情况判定。y == x 时要求该键的计数至少为 2，因为需要两个不同位置的元素；y != x 时只要 y 在表中即可，此时两者必然来自不同的添加。这两个分支必须都写全，只写其中一个都会漏解或误判。

一旦命中立即返回真，全部遍历完仍未命中返回假。提前返回能让大多数查询在扫到前几个键时就结束。

走一遍一组操作：依次 add(1)、add(3)、add(5)，然后 find(4)、find(7)。

三次添加后计数表是 {1: 1, 3: 1, 5: 1}。find(4)：取键 1，y = 3，y != x 且 3 在表中，返回真——对应元素 1 与 3。find(7)：取键 1，y = 6 不在表中；取键 3，y = 4 不在表中；取键 5，y = 2 不在表中；遍历结束返回假。

再走一组体现自我配对的操作：add(3)、find(6)、add(3)、find(6)。

第一次 add(3) 后计数表是 {3: 1}。find(6)：取键 3，y = 3 与 x 相等，检查计数为 1 未达到 2，不算命中；遍历结束返回假——正确，因为只有一个 3，不能和自己配对。第二次 add(3) 后计数表是 {3: 2}。再 find(6)：取键 3，y = 3 相等，计数为 2 满足条件，返回真——正确，两个 3 来自两次不同的添加。

若把自我配对的分支写成「只要 y 在表中就返回真」，第一次 find(6) 就会错误地返回真；若干脆不处理这个分支、遇到 y == x 就跳过，第二次 find(6) 又会错误地返回假。两个方向的错误各对应一半用例，必须都覆盖。

代码实现

import java.util.HashMap;
import java.util.Map;

class TwoSum {

    // 用计数而非布尔标记，才能判定「两个相同数值」的配对。
    private Map<Long, Integer> countMap;

    public TwoSum() {
        countMap = new HashMap<>();
    }

    public void add(int number) {
        long key = number;
        countMap.put(key, countMap.getOrDefault(key, 0) + 1);
    }

    public boolean find(int value) {
        for (Map.Entry<Long, Integer> entry : countMap.entrySet()) {
            long num = entry.getKey();
            long complement = (long) value - num;

            if (complement == num) {
                // 自我配对必须有两份。
                if (entry.getValue() >= 2) {
                    return true;
                }
            } else {
                if (countMap.containsKey(complement)) {
                    return true;
                }
            }
        }
        return false;
    }
}

type TwoSum struct {
	// 用计数而非布尔标记，才能判定「两个相同数值」的配对。
	countMap map[int64]int
}

func Constructor() TwoSum {
	return TwoSum{countMap: make(map[int64]int)}
}

func (t *TwoSum) Add(number int) {
	t.countMap[int64(number)]++
}

func (t *TwoSum) Find(value int) bool {
	for num, cnt := range t.countMap {
		complement := int64(value) - num

		if complement == num {
			// 自我配对必须有两份。
			if cnt >= 2 {
				return true
			}
		} else {
			if _, ok := t.countMap[complement]; ok {
				return true
			}
		}
	}
	return false
}

复杂度分析

时间复杂度：add 均摊 $O(1)$，只做一次哈希查找与一次自增；find 是 $O(d)$，$d$ 为当前不同数值的个数，最坏等于添加次数 $n$。注意 find 的成本与「不同值的个数」而非「总添加次数」挂钩，反复添加同一个数不会让查询变慢。

空间复杂度：$O(d)$，计数表中每个不同数值占一个条目。相比保存全部元素的列表，重复元素被压缩成一个计数，空间更省。

关键点总结

「两数之和」的通用降维手法是固定一个、反查另一个：因为配对值由目标唯一确定，枚举一个数就够了。这条思路从 1 题一直贯穿到 15、18、454。

容器选计数表而非集合，唯一目的是支撑自我配对的判定。设计数据结构时，「需要区分出现一次还是多次」是选择计数结构的典型信号。

遍历键集合而不是原始序列，让重复元素不影响查询成本。这是把「去重」这件事交给数据结构承担，而不是在算法里临时处理。

自我配对与异值配对必须写成两个互斥分支，任何一支缺失都会在一半用例上出错，而且这两类用例通常一个返回真、一个返回假，靠单个测试很难同时暴露。

易错点总结

错误写法：用 Set 代替计数表。用例：add(3) 后 find(6) → 集合里有 3，配对值也是 3，判定为存在并返回真，正确答案是假，因为只有一个 3。

错误写法：不区分自我配对，一律写成 containsKey(value - num)。用例：add(0) 后 find(0) → 配对值 0 在表中，返回真，正确答案是假。

错误写法：遇到 complement == num 就直接跳过。用例：add(3)、add(3) 后 find(6) → 唯一能命中的分支被跳过，返回假，正确答案是真。

错误写法：自我配对时判断条件写成 > 2。用例：add(3)、add(3) 后 find(6) → 计数为 2 不满足严格大于，返回假，正确答案是真。

错误写法：add 时用 put(number, 1) 而不是自增。用例：add(3)、add(3) 后 find(6) → 计数被覆盖成 1，自我配对判定失败，返回假，正确答案是真。

错误写法：把元素存进列表并在 find 里做双重循环。用例：连续 $10^4$ 次 add 后再做 $10^4$ 次 find → 单次查询 $10^8$ 量级，必然超时；思路正确但复杂度不过关。

错误写法：把列表排序后用双指针查找，但每次 find 都重新排一次。用例：$10^4$ 次交替的 add 与 find → 每次查询都付出 $O(n \log n)$ 的排序成本，比线性扫描还慢。

错误写法：find 中先返回假再继续遍历（把 return false 写在循环体内）。用例：add(1)、add(3) 后 find(4) → 第一个键若不命中就立刻返回假，永远只检查一个键，正确答案是真。

错误写法：用 32 位 int 直接计算 value - num。用例：依次加入 1 与 Integer.MAX_VALUE，再查找 Integer.MIN_VALUE；补数计算会溢出成 Integer.MAX_VALUE，错误返回真，但两数的数学和是 2147483648。代码把键和补数提升到 64 位，避免溢出伪造配对。

相似题目

题目	难度	考察点
1. 两数之和	简单	一次性数组且要求返回下标，可以边遍历边写入表，无需处理在线追加
167. 两数之和 II - 输入有序数组	中等	有序前提下用双指针做到 $O(1)$ 额外空间，展示排序如何替代哈希
653. 两数之和 IV - 输入二叉搜索树	简单	数据装在 BST 里，可中序展开后双指针，也可边遍历边查集合
1099. 小于 K 的两数之和	简单	目标从「等于」变成「小于且最大」，哈希失效，必须排序后双指针
15. 三数之和	中等	固定一个数后转化为两数之和，难点转移到排序去重与指针跳过重复值
454. 四数相加 II	中等	分成两半各自打表再对撞，是「固定一半查另一半」思路的规模化应用
705. 设计哈希集合	简单	要求手写哈希表本身，考点在冲突处理与扩容而非上层算法
703. 数据流中的第 K 大元素	简单	同为在线数据流的设计题，用小顶堆维护候选，同样要权衡两个接口的复杂度