algorithm - 在总和为某个整数 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 系数是给定数组中数字 i 的出现次数。现在我们可以使用傅立叶快速变换在 s 时间内找到这个多项式的平方(我称之为 O(n log n) )。 i 的第 s 系数恰好是总和为 i 的元素对的数量。

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

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

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

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

2. 找到这样一个元素，它有一对总和为 X 的元素。

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

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