C++如何在O(nlog(n))的时间内检查此条件？

Question

假设您有一个排序的向量{x_i}_i=1ⁿ，其元素均为正数且不包含平局（=此向量中没有两个元素相同）。

我正在寻找检查以下内容的最聪明方法：

对于所有1 <= i != j != k <= n，2x_i - x_j - x_k != 0。

我有一种预感，这可以在O(nlog n)的时间内完成，或者以比朴素更好的方式进行，可能使用类似于this question中开发的策略。

请记住，x的条目都是正数并且已排序，因此x_k+k_j的条目也已排序。

附言：我正在寻找算法/语言不可知的想法。 C++标签主要用于在需要利用某些智能缓存策略时执行此操作。

编辑：

@liori提出了一个很好的观点，对于给定的i查找(j,k)对的时间复杂度为O(n)，使用类似于回答相关问题的最后一次迭代的算法。问题在于是否可以比朴素地进行更高效地组合这些许多O(n)步骤。例如，我们可以在O(n)时间内找到给定索引i的(j,k)对。但是我们需要再次考虑j'<=j和k'<=k的所有条目作为下一个索引i'=i+1的候选项吗？这些节省的时间是否会累加？

- user189035

---

是的，但我已经重新添加了它，不用担心 :-) 关于并发编辑，SO系统还有一些需要改进的地方。 - Angew is no longer proud of SO

你希望那些“!=”是可传递的吗？ - jxh

@jxh：如果 i=k，则 2x_i = x_i + x_j，因此 x_i = x_j。由于没有平局，这迫使 i=j。所以，这没关系。 - liori

有一篇由Baran、Demaine和Patrascu撰写的论文，针对3SUM问题在允许一定程度并行计算（字RAM）的奇特计算模型下获得了大约O(n^2/log^2 n)的上界。我怀疑你无法取得更好的结果。 - tmyklebu

你有两个O(n^2)的答案，一个使用O(n^2)的空间，另一个使用O(1)的空间。我认为你把勾选标记放在了错误的答案上。 - Mark Ransom

Answer 1

请注意，“sorted”对你没有帮助，因为基于比较的排序可以在O(n log n)时间内对任何n个数字的列表进行排序。

我无法完全证明这个问题的3SUM-完备性，但Jeff Erickson的这篇论文证明，在一种受限的计算模型中，不存在解决此问题的次二次算法。这并不是一个不可能的证明，但Erickson使用的计算模型允许我想到的所有合理技巧。特别地，我怀疑这个网站上的任何人都不会在不久的将来提出一个O(n log n)的算法来解决你的问题。

在某些允许有限并行性的计算模型中，存在一个次二次算法来解决3SUM问题。我相信Baran、Demaine和Patrascu的这篇论文是首先展示这一点的。

- tmyklebu

Answer 2

以下算法可以实现二次时间复杂度：

对于每个i∈{1, …, N}：

1. 令 j=i-1, k=i+1。
2. 如果 j<1 或者 k>N，则停止。
3. 计算 d=(x_i - x_j) - (x_k - x_i)
4. 如果 d=0，则停止。
5. 如果 d<0，则 j--。
6. 如果 d>0，则 k++。
7. 重复步骤2。

该算法利用了 x_i 必须与 x_j（x_i - x_j 表达式）和 x_k（x_k - x_i）相距相等的事实。此外，由于向量已排序，因此差异随着索引之间的差异增加而增加。

- liori

---

@Abhijit：我在想，一旦对于给定的$i$找到了一对$(j,k)$，是否这会告诉我们有关下一个指数$i'=i+1$的新一对$(j',k')$的任何信息，因为$x(i')>x(i)$。这本质上就是我的问题。 - user189035

我不相信那个网站，我看不出来第一个算法是对数的，当使用一个数组 [0,2,4,...,2N] 查找2N-1（在那里是不可能找到的）时，它明显需要线性步骤数量。 - liori

你真的认为在这种问题上声誉有意义吗？ - Javi

@user189035：说实话，我想不出在迭代之间重复使用计算的简单方法。整数是棘手的问题，例如子集和问题属于 NP… - liori

@liori：我会稍微等待一下问题。其实我没想到能得到如此快速的答案。我确实需要自己做更多的研究。 - user189035

Answer 3

这是另一个 Ο(n²) 算法。一个哈希表被填充了和及其对应配对。由于你指定了 c++，所以以下代码的数组索引从0开始，而不是你问题陈述中的1：

typedef std::pair<int, int> xy;
typedef std::unordered_map<int, xy> sums;

template <int N>
xy func (const int (&a)[N]) {
    sums s(2*N*N);
    for (int lo = 0; lo < N-2; ++lo) {
        for (int hi = lo+2; hi < N; ++hi) {
            int ss = a[lo] + a[hi];
            if (ss % 2 == 0) s[ss] = xy(lo, hi);
        }
    }
    for (int i = 1; i < N-1; ++i) {
        if (s.find(2*a[i]) != s.end()) return s[2*a[i]];
    }
    return xy(0, 0);
}

这个算法明确说明了求和的搜索空间是Ο(n²)。

您可能认为可以通过找到一个次线性的算法来确定一个给定的x_i是否与一对（x_j，x_k）匹配来得到一个次二次的算法。相反，重新思考问题，将其视为确定一个给定的一对（x_j，x_k）是否匹配一个x_i。如果您从这个角度考虑，应该更清楚地意识到需要最坏情况下二次算法才能确定没有一对满足您的条件。

- jxh