我想使用 Hashmap 找到数组中总和为某个数字 X 的所有对。我知 Prop 有 O(n^2) 复杂度的基本解决方案,但我在某处读到 hashmap 可以提供 O(n)解决方案。我不知道如何使用 hashmap 来实现解决方案。有人可以为我提供有关如何执行此操作的伪代码吗?
最佳答案
如果您要使用类似 std::set
的东西,那么集合中的所有值都将是唯一的。这将允许您遍历集合并从所需值中减去以确定您需要的其他值。然后您可以测试该值是否存在于集合中。操作看起来像这样:
- 将迭代器设置为集合中的第一个元素
- 获取集合中第一个元素的值
- 用期望值减去值得到需要的值
- 测试集合以查看所需的值是否在集合中
- 如果是记录两个值
- 增加迭代器并从#2 开始重复,直到到达集合的末尾
关于c++ - 如何在 C++ 中使用 Hashmap 查找任意随机数组中总和为特定值的所有对,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21713129/