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) - 只需考虑如何使用单调性属性。