如何知道我们的数组中存在三角形三元组？

Question

我被困在解决以下面试实践问题:
我必须写一个函数:

int triangle(int[] A);

给定零索引数组A由N整数组成,1如果存在三重(P,Q,R)则返回0 < P < Q < R < N.

A[P] + A[Q] > A[R],  
A[Q] + A[R] > A[P],  
A[R] + A[P] > A[Q].

0如果不存在这样的三元组,则该函数应该返回.假设0 < N < 100,000.假设数组的每个元素都是范围内的整数[-1,000,000..1,000,000].

例如,给定的数组就是A这样

A[0]=10, A[1]=2, A[2]=5, A[3]=1, A[4]=8, A[5]=20

函数应该返回1,因为三元组(0, 2, 4)满足所有必需条件.

对于A这样的阵列

A[0]=10, A[1]=50, A[2]=5, A[3]=1

该函数应该返回0.

如果我做一个三重循环,这将非常非常慢(复杂性:) O(n^3).我想也许可以用来存储数组的额外副本并对其进行排序,并使用二进制搜索特定的数字.但我不知道如何解决这个问题.
有任何想法吗？

Answer 1

首先,您可以对序列进行排序.对于排序序列这足以检查A[i] + A[j] > A[k]了i < j < k,因为A[i] + A[k] > A[k] > A[j]等,因此其他2个不平等自动属实.

(从现在开始,i < j < k.)

接下来,它足以检查它A[i] + A[j] > A[j+1],因为其他A[k]的甚至更大(所以如果不平等对某些人k来说也是如此,它也适用k = j + 1).

接下来,它足以检查A[j-1] + A[j] > A[j+1],因为其他A[i]甚至更小(所以如果不平等对某些人i来说也是如此,那么它也适用i = j - 1).

所以,你只需要一个线性检查:你需要检查至少有一个是否j A[j-1] + A[j] > A[j+1]成立.

一共O(N log N) {sorting} + O(N) {check} = O(N log N).

解决有关负数的评论:实际上,这是我在原始解决方案中未考虑的内容.考虑到负数不会改变解决方案,因为没有负数可以是三角形三重的一部分.事实上,如果A[i],A[j]和A[k]三重形成一个三角形,然后A[i] + A[j] > A[k],A[i] + A[k] > A[j],这意味着2 * A[i] + A[j] + A[k] > A[k] + A[j],因此2 * A[i] > 0,使A[i] > 0与由对称性A[j] > 0,A[k] > 0.

这意味着我们可以安全地从序列中删除负数和零,这O(log n)在排序后完成.

Answer 2

在Java中:

public int triangle2(int[] A) {

    if (null == A)
        return 0;
    if (A.length < 3)
        return 0;

    Arrays.sort(A);

    for (int i = 0; i < A.length - 2 && A[i] > 0; i++) {
        if (A[i] + A[i + 1] > A[i + 2])
            return 1;
    }

    return 0;

}