algorithm - 排序序列中的三角形数

Question

给定 n 的严格递增序列正整数 A(1) < A(2) < ... < A(n) .我们需要找到边长为 3 的三角形的数量这个序列的不同元素。

自 n <= 6000 ，检查每个可能的组合还不够快。有没有更好的算法？感谢您的帮助。

我的伪代码:

for i from 0 till n - 2
    for j from i+1 till n-1
        for k from j+1 till n
            if A[i] + A[j] > A[k] then count += 1
            else break

Answer 1

1. 您可以排除第三个循环并使用二进制搜索查找最大 k 值。复杂度为 O(N^2*Log(N)
2. 您可以达到更好的时间 - O(N^2) - 只需考虑如何使用单调性属性即可。