用unordered_set边遍历边存值,o(n)解决两数乘积为k问题;需特判k=0、a=0、整除性、符号、int_min/-1溢出,统一转long long计算防溢出。

用 unordered_set 辅助,O(n) 时间搞定
直接遍历数组,对每个元素 a,检查 k / a 是否已存在(注意整除和零的处理)。核心是边遍历边把见过的数存进 unordered_set,避免双重循环。
关键点在于:不是找「和」而是找「积」,所以不能简单用两数之和的思路照搬;必须考虑整除性、符号、零值这三类边界。
- 若
k == 0:只需检查数组中是否有至少一个0(因为任意数 × 0 = 0),且另一个因子可以是任意数——但实际只要有一个0就够了,除非题目要求两个**不同位置**的数,此时需至少两个0 - 若
a == 0且k != 0:跳过,因为 0 无法作为乘数得到非零k - 否则检查
k % a == 0是否成立,再查seen.find(k / a) != seen.end();不先取模就除会导致整数溢出或浮点误差
处理负数和溢出的细节必须写死
C++ 整数除法向零截断,-5 / 2 == -2,但 -2 * 2 == -4 ≠ -5,所以不能只靠 k / a 查表——必须验证整除性。另外 INT_MIN 被 -1 除会溢出,得提前拦截。
常见错误是写成 if (seen.count(k / a)) 而没判 a != 0 && k % a == 0,结果在 k=7, a=3 时误判 7/3==2 存在而返回 true。
- 加卫语句:
if (a == 0) { if (k == 0) return true; continue; } - 再判整除:
if (k % a != 0) continue; - 最后才查集合:
if (seen.find(k / a) != seen.end()) return true; - 特别防溢出:
if (a == -1 && k == INT_MIN) continue;(因为INT_MIN / -1溢出)
用 long long 避免中间计算溢出
即使输入是 int 数组,k 和 a 相乘或相除过程可能溢出 int 范围。比如 a = -100000, k = 2000000000,k / a 是 -20000,看似安全,但 k % a 计算时若用 int 可能 UB。
- 统一把
a和k转成long long再算:long long la = a, lk = k; - 所有模和除操作都在
long long上进行:if (la != 0 && lk % la == 0) -
unordered_set<long long></long>存值,避免类型隐式转换出错
别忘了重复元素和索引限制
题目若要求「两个不同下标的元素」,那不能用同一个元素两次——但用 unordered_set 边插边查天然满足这点,因为查的是之前位置的数。唯一例外是 k == a * a 且只有一个 a 出现时,不能算成功。
如果题目明确要两个**不同位置**且允许相同值(如数组 [2, 2], k=4 应返回 true),当前方法没问题;但如果只给一个 2,就不能匹配。不需要额外计数,除非题目要求统计对数。
- 不需要用
map记频次,除非你要支持「同一元素用两次」这种非常规需求 - 如果题目说「任意两个数」,默认指不同下标,当前逻辑已覆盖
- 测试用例务必包含:
[1,2,3,4], k=6(true)、[1,2,3], k=7(false)、[0,1], k=0(true)、[-1,2,-3], k=3(true)
实际最易被忽略的是整除判断顺序:必须先确保 a != 0,再算 k % a,否则运行时崩溃。C++ 不做除零检查,段错误直接来。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











