给定一个排序好的数组[1..n],每个元素范围在1到2n之间。有没有一种方法可以找到三元组,使它们的和为给定整数x。我知道O(n^2)的解决方案。是否有比n^2更好的算法。
给定一个排序好的数组[1..n],每个元素范围在1到2n之间。有没有一种方法可以找到三元组,使它们的和为给定整数x。我知道O(n^2)的解决方案。是否有比n^2更好的算法。
O(n)
,可以达到 O(n log n)
的时间复杂度。
对于每个 1 <= y <= 4 * n
,找出元素加和等于 y
的对数。我们可以创建一个二次幂多项式,其中该多项式的第 i
个系数是给定数组中数字 i
出现的次数。接下来使用 Fourier's Fast Transform 可以在 O(n log n)
时间内找到这个多项式的平方(我将其称为 s
)。s
的第 i
个系数恰好就是元素加和等于 i
的对数。
现在我们可以遍历给定的数组。假设当前元素是 a
。然后只需要检查元素加和等于 X - a
的对数。我们已经在步骤 1) 中完成了此操作。
如果所有三元组必须由不同的元素组成,则需要减去相加等于 X
但包含重复的三元组数量。我们也可以在 O(n log n)
的时间内完成此操作(对于由三个相等元素组成的三元组,我们只需要减去给定数组中 X / 3
的出现次数即可。对于具有一次重复的三元组,我们只需遍历重复出现两次的元素(a
),并减去 X - 2 * a
的出现次数)。
如果我们需要找到一个三元组本身而不仅仅是计算它们,则可以执行以下步骤:
根据上述建议计算三元组和对数。
找到这样的元素,其中与其加和等于X
的有一对。
找到两个元素,使它们的和为所需的这一对的和。
所有这些步骤都可以在线性时间内完成(利用所有总和都是 O(n)
的事实)。