我们需要在一个数组中找到一对数字，其总和等于给定值。
A = {6,4,5,7,9,1,2}
总和 = 10 那么这些对是 - {6,4} , {9,1}
我有两个解决方案。
- O(nlogn) 解决方案 - 使用 2 个迭代器(开始和结束)排序 + 校验和。
- O(n) 解决方案 - 散列数组。然后检查哈希表中是否存在
sum-hash[i]。
但是，问题是第二个解决方案虽然是 O(n) 时间，但也使用 O(n) 空间。
所以，我想知道我们是否可以在 O(n) 时间和 O(1) 空间内完成。这不是家庭作业!
最佳答案
使用就地基数排序和 OP 的第一个解决方案，两个迭代器相互靠近。
如果数组中的数字不是某种多精度数字，而是例如 32 位整数，您可以在 2*32 遍中对它们进行排序，几乎不需要额外的空间(每次 1 位)。或 2*8 遍和 16 个整数计数器(每遍 4 位)。
2 个迭代器解决方案的详细信息:
第一个迭代器最初指向已排序数组的第一个元素并向前推进。第二个迭代器最初指向数组的最后一个元素并向后推进。
如果迭代器引用的元素总和小于所需值，则推进第一个迭代器。如果它大于所需值，则推进第二个迭代器。如果等于要求的值，则成功。
只需要一次pass，所以时间复杂度是O(n)。空间复杂度为 O(1)。如果使用基数排序，整个算法的复杂度是一样的。
如果您对相关问题(大于 2 个数字的总和)感兴趣，请参阅 "Sum-subset with a fixed subset size"和 "Finding three elements in an array whose sum is closest to an given number" .
关于algorithm - 在未排序的数组中找到 2 个等于给定总和的数字，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9656789/