在数组中找到三个数，它们的和为整数X。

Question

给定一个排序好的数组[1..n]，每个元素范围在1到2n之间。有没有一种方法可以找到三元组，使它们的和为给定整数x。我知道O(n^2)的解决方案。是否有比n^2更好的算法。

- Chandan

---

相关：固定子集大小的子集求和 - amit

根据快速搜索，看起来可以在O(n + n log n)的时间内完成：http://en.wikipedia.org/wiki/3SUM#Non-zero_sum - Noyo

什么是O(n^2)的解决方案？ - thang

@thang：http://en.wikipedia.org/wiki/3SUM#Quadratic_algorithm - Noyo

@Noyo，哦，这很酷。我猜对于r-sum，当r为偶数时，它是O(n^(r/2) log n)，当r为奇数时，它是O(n^((r+1)/2))。使用这些技巧。我认为3sum的绝对理论下限大约是O(n^1.5 (log n)^.5)。这是通过计算需要定位三元组的比较次数来实现的。 - thang

Answer 1

使用每个元素的最大值为O(n)，可以达到 O(n log n) 的时间复杂度。

1. 对于每个 1 <= y <= 4 * n，找出元素加和等于 y 的对数。我们可以创建一个二次幂多项式，其中该多项式的第 i 个系数是给定数组中数字 i 出现的次数。接下来使用 Fourier's Fast Transform 可以在 O(n log n) 时间内找到这个多项式的平方（我将其称为 s）。s 的第 i 个系数恰好就是元素加和等于 i 的对数。

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

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

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

1. 根据上述建议计算三元组和对数。

2. 找到这样的元素，其中与其加和等于X的有一对。

3. 找到两个元素，使它们的和为所需的这一对的和。

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

- kraskevich

---

你好，你的第一步不太清楚。能否请提供一个简单的例子？ - Chandan

@ChandanParameswaraiah 假设我们有一个数组 {1, 1, 2}。多项式是 {0, 2, 1}。现在我们只需要将它自己相乘即可。 - kraskevich

请不要介意。我觉得有些困难。假设我有一个数组{1,2,3,8,10}，并且x等于11。我需要找到这个三元组（在这个例子中是1、2、8）。你能否用这个例子说明一下这个算法？ - Chandan

Answer 2

您的问题显然是非零和变体的3SUM问题。

根据文章第二段所述，因为您事先知道整数的可能范围，所以可以实现比一般情况更低的下限：

当元素是范围内的整数[-N, ..., N]时，可以通过将输入集合S表示为位向量，使用快速傅里叶变换计算所有成对求和的集合S + S 作为离散卷积，最后将此集合与-S 进行比较，从而在O(n + N log N)时间内解决3SUM问题。

在您的情况下，在运行算法之前，您需要通过减去n + X/3来预处理数组。

需要注意的一点是，该算法假定您正在使用一组数字，我不确定如果您的数组可能包含重复数字是否会对运行时间产生任何影响。

- Noyo

---

问题在于，如果您有一个由10个整数组成的数组，范围从MININT到MAXINT，那么您的运行时间为MAXINT log MAXINT，这比1000的暴力力量还要糟糕。我想原始帖子确实说了2n范围，所以这不是一个问题。 - thang