算法：检查数组S和T中是否存在整数s和t，使得s+t=k（k为给定数字）。简化版：检查数组S和T中是否有两个数的和等于给定数字k。

Question

6

我正在尝试制作一个算法，它接受两个包含n个整数的数组S和T以及整数k。该算法会检查数组中是否有整数s和t，使得它们的和等于k。(s在S中，t在T中。) 该算法的运行时间应为O(n log n)。

我试图想出一些方法来排序数组T，并使用for循环遍历S，然后使用二进制搜索来查找是否存在整数等于k-S [i]，对于S中的每个元素。但是我认为这将始终具有大于n log n的运行时间。

我不是在寻求编写代码的人。只是想在这里获取一些想法。

- user622194

如果S和T中的整数被限制在大小为m的范围内，您可以设计一个时间复杂度为O(n)，空间复杂度为O(m)的算法。 - danr

6个回答

3

对两个数组进行排序。从相反的方向逐步遍历它们。如果两个元素的总和小于k，则将“增加”指针前进；如果大于k，则将减少指针。这种方法可能比仅对一个数组进行排序慢一些，但最终的传递肯定更快。而且可能更短，因为可以跳过两个数组的头部和尾部（剪枝）。

- wildplasser

不需要二分查找，万岁！ - danr

这与Aaron McDaid的相同，但他在时间上击败了我。 - wildplasser

2

你指定的算法实际上确实具有O(n log n)的运行时，假设两个数组中的总元素数量为O(n)。你可以在这里看到这一点：

第一步需要O(n log n)的时间，第二步由O(n)次O(log n)算法迭代组成，因此也需要O(n log n)的时间。由于O(n log n) + O(n log n) = O(n log n)，所以您的算法在O(n log n)的时间内运行。看起来你已经得到了你想要的算法！

希望这能帮到你！

- templatetypedef

1

你的方法看起来是正确的；首先对数组进行排序，这是两个O(n log n)的操作，然后执行n个二分查找，每个查找的时间复杂度为O(log n)。

- danr

1

排序是O(n log n)。然后，对于每个O(n)的前n个元素，您需要进行一个O(log n)的搜索以查找匹配的元素。总体上听起来像是O(n log n)（因为对于任何函数f，O(f)+O(f)=O(f)）。

- Ted Hopp

0

另一种方法：使用哈希表（O(N)）存储其中一个数组。对于另一个数组执行线性遍历（O(N)），并对每个元素在哈希表中查找k-elem。总运行时间：2 * O(N) := O(N)。获利！

- wildplasser

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aaron McDaid · Accepted Answer

将这两个列表排序，时间复杂度为O(n log n)。

然后设置两个迭代器。一个迭代器从S中的最小值开始，并沿着递增的值向前移动。另一个迭代器从T中的最大值开始，并沿着递减的值迭代。

重复以下步骤：

这个第二阶段最多只需进行2N次推进，因此时间复杂度为O(n)。因此，总复杂度为O(n log n)。

这与重复二分搜索具有相同的复杂度，但是这个算法应该更快，特别是对于大的n。

算法：检查数组S和T中是否存在整数s和t，使得s+t=k（k为给定数字）。 简化版：检查数组S和T中是否有两个数的和等于给定数字k。