检查数组S和T中是否为整数s和t的算法,如果k给定数,则s + t = k

Question

我试图制作采用两个数组的算法,S和T为n个整数和整数k.该算法检查数组是否具有整数s和t,因此s + t = k.(S中的s和T中的s).该算法应该具有O(n log n)的运行时间.

试图想到一些排序数组T并使用循环来通过S并使用二进制搜索来查看是否为S中的每个元素找到k-S [i]之类的整数但是总是会有大于运行时间的运行时间. n log n,我想.

不是在找人写代码.只是要求在这里得到一些想法.

Answer 1

对两个列表进行排序,这是O(n log n).

然后设置两个迭代器.一个迭代器从S 中的最低值开始,然后继续前进到S中不断增加的值.另一个迭代器从T 中的最高值开始并迭代不断减小的值.

重复以下步骤:

• 如果当前值总和大于k的数字,则推进T迭代器.这应该减少总和.
• 如果当前值总和为小于k的数字,则推进S迭代器.这应该增加总和.
• 如果当前值总和为k,则退出并成功.

第二阶段最多应该导致2N的进展,因此是O(n).因此总复杂度为O(n log n).

这与重复二进制搜索具有相同的复杂性,但是该算法应该更快,特别是对于大n.