algorithm - 分而治之问题

Question

给定一个集合 M，找出是否有一对数 (a,b)，都属于 M，并且 a+b=x，其中 x 是先前指定的参数。该问题应使用 O(n * log n) 中的 Divide et Impera 来解决。可能问题应该分成两个半大小的子问题，然后在 O(n) 中重新组合结果。

我想要给定问题的伪代码或解决它的提示。

Answer 1

不确定这是否符合您的要求，但是：

1. 对集合进行合并排序（这使用分而治之）。
2. 从集合的第一个和最后一个元素开始，并将它们的总和与 x 进行比较。如果总和相等，你就完成了。如果总和较大，则递减到倒数第二个元素，如果总和较小，则递增到第二个元素。
3. 重复第二步，从排序集的末端到中心，直到找到总和为 x 的元素，或者没有更多元素。

分治排序是 O(n lg n)，遍历排序集是 O(n)，因此总复杂度是 O(n lg n)。

Ed：总和到 x，而不是 M。

Answer 2

如果您对 M 进行排序（在 O(n log n) 中，使用 D&I），您可以检查线性时间是否有一对总和正确。（提示：两个指针）。

如果您认为这不会算作 D&I 解决方案，您可以将检查步骤折叠到排序的合并步骤中，如果找到匹配项，请提前退出。

加法：如果您在合并期间进行检查，您最终会执行 O(n log n) 加和比较步骤而不是 O(n) - 当然，除了常数之外，这不会恶化渐近运行时间因素。