在数组中查找三元组,其总和为整数X.

Question

给定一个排序数组[1..n],其中每个元素的范围从1到2n.有没有办法找到三元组,其和为整数x.我知道O(n ^ 2)解决方案.有没有比n ^ 2更好的算法.

Answer 1

可以O(n log n)使用每个元素的最大值为 的事实来实现时间复杂度O(n)。

1. 对于每个1 <= y <= 4 * n，让我们找出总和为 的元素对的数量y。我们可以创建幂多项式2 * n，其中i该多项式的第 -th 个系数是i给定数组中数字出现的次数。现在我们可以使用傅立叶快速变换及时找到s这个多项式的平方（我称之为）O(n log n)。的i-th 系数s正好是总和为 的元素对的数量i。

2. 现在我们可以迭代给定的数组。让我们假设当前元素是a。然后我们只需要检查总和为 的对数X - a。我们已经在步骤 1) 中完成了。

如果所有三元组必须由不同的元素组成，我们需要减去相加X但包含重复项的此类三元组的数量。我们也可以O(n log n)及时完成（对于由三个相等元素组成的三元组，我们只需要减去X / 3给定数组中出现的次数。对于有一个重复的三元组，我们可以迭代重复两次的元素( a) 并减去 ) 的出现次数X - 2 * a。

如果我们需要找到一个三元组本身，而不仅仅是计算它们，我们可以执行以下操作：

1. 按照上面的建议计算三胞胎和双胞胎的数量。

2. 找到这样一个元素，它有一对X与它相加。

3. 找到两个元素的总和为该对的所需总和。

所有这些步骤都可以在线性时间内完成（使用所有和都是 的事实O(n)）。