LeetCode 170. 两数之和 III - 数据结构设计
题目描述
题意分析
容器支持不断添加整数，以及查询当前是否存在两个数之和等于指定目标。两个数必须来自两次不同的添加，但数值可以相同。查询只判断是否存在，不需要返回下标，也不会消耗已经添加的数字。
解法：哈希频次 + 补数查询
核心思路
[!blue]
按数值保存频次，枚举一个加数后唯一确定另一个。countMap[x]表示数字x已添加多少次。对于目标value和已有数字x，另一个加数必须是value-x，因此只需查一次哈希表，无需再遍历第二个加数。若补数不同于
x，两个值都存在就对应两次不同的添加，可以配对；若补数等于x，查到这个键只能说明至少有一份，必须进一步要求频次不少于 2，才能避免重复使用同一个元素。任意合法数对中的一个值都会在枚举中出现，它的另一个值又恰好是查询到的补数，所以全部不同值检查完仍未命中时，才能确认没有答案。重复添加只改变频次，不需要保存重复键；重复查询也只读取频次，容器状态保持不变。
解题步骤
- 构造时初始化空频次表。
add(number)将对应频次加一，首次出现时从 0 开始累加。find(value)遍历每个不同值，计算补数，并分别检查异值存在性或同值的两份要求。- 找到任一合法配对立即返回
true，全部检查完才返回false。空容器和只有一份数字的容器都无法组成数对；两份相同数字则可以配成其两倍。补数使用
long或int64计算，先转换到宽整数再做减法，避免目标与已有值相减时发生窄整数溢出。
代码实现
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+1)$，d 为当前不同值数量。
- 空间复杂度：$O(d+1)$，相同值压缩为计数。
关键点总结
[!green]
- 同值配对需要两份，异值配对只需分别存在。
- 补数由目标唯一确定，避免枚举全部数对。
- 查询失败只能在所有不同值检查完之后确定。
易错点总结
[!yellow]
- 用集合只记录存在性：无法区分一份与两份相同值。
- add 总是将计数设为一：重复添加的信息丢失。
- 补数等于自身时直接跳过：会漏掉两份相同值的合法情况。
- 一次查找未命中就返回 false：其他值仍可能组成目标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1. 两数之和 | 简单 | 原题只查一次目标和，本题支持多次add与find，需要长期维护频次并处理同值配对。 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 如果数据可批量排序，可通过两端指针查询；动态插入场景要权衡维护成本。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！