c++ - 三角形 : Determine if an array includes a triangular triplet (Codility)

Question

这是 Codility 的三角问题:

A zero-indexed array A consisting of N integers is given.
A triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

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

Write a function:

int solution(vector<int> &A);  

that, given a zero-indexed array A consisting of N integers, returns 1 if there exists a triangular triplet for this array and returns 0 otherwise.

For example, given array A such that:
A[0] = 10, A[1] = 2, A[2] = 5, A[3] = 1, A[4] = 8, A[5] = 20 Triplet (0, 2, 4) is triangular, the function should return 1.

Given array A such that:
A[0] = 10, A[1] = 50, A[2] = 5, A[3] = 1
function should return 0.

Assume that:

N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

这是我在 C++ 中的解决方案:

int solution(vector<int> &A) {
    if(A.size()<3) return 0;

    sort(A.begin(), A.end());

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

我查看了那里的评论，所有的解决方案似乎都与我的相似。
然而，别人都说100分，我却只有93分。
我得到了所有的测试用例，除了一个:

extreme_arith_overflow1
overflow test, 3 MAXINTs

我假设这个案例有这样的输入:
[2147483647, 2147483647, 2147483647]

所以我将其添加到自定义测试用例中，结果明明应为 1 时答案却为 0。
我也试了[1900000000, 1900000000, 1900000000]，答案还是0。
但是，[1000000000, 1000000000, 1000000000] 是正确的，答案为 1。

谁能告诉我为什么会出现这个结果？
非常感谢。

Answer 1

我的 Java 解决方案具有 100/100 和 O(N*log(N)) 的时间复杂度

注释说明逻辑

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

    int N = A.length;
    if (N < 3) return 0;
    Arrays.sort(A);

    for (int i = 0; i < N - 2; i++) {

        /**
         * Since the array is sorted A[i + 2] is always greater or equal to previous values
         * So A[i + 2] + A[i] > A[i + 1] ALWAYS
         * As well ass A[i + 2] + A[i + 1] > A[i] ALWAYS
         * Therefore no need to check those. We only need to check if A[i] + A[i + 1] > A[i + 2]?
         * Since in case of A[i] + A[i + 1] > MAXINT the code would strike an overflow (ie the result will be greater than allowed integer limit)
         * We'll modify the formula to an equivalent A[i] > A[i + 2] - A[i + 1]
         * And inspect it there
         */
        if (A[i] >= 0 && A[i] > A[i + 2] - A[i + 1]) {

            return 1;
        }
    }

    return 0;
}

基本上，当您检查整数的 X + Y 值时，如果大于整数限制，代码将因溢出而失败。因此，我们可以简单地检查等效语句 if X > Z - Y，而不是检查 if X + Y > Z(简单的数学不是吗？)。或者，您始终可以使用 long，但这在内存方面会是一个更糟糕的解决方案。

还要确保跳过负数，因为三角形不能有负边值。

干杯