三角形：判断一个数组是否包含三角形三元组（Codility）

Question

这是 Codility 的三角形问题：

给出了一个由 N 个整数组成的零索引数组 A。

三元组 (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]。

写一个函数：

>  int solution(vector<int> &A);
>
> ```
>
> 即，给定一个由 N 个整数组成的零索引数组 A，如果该数组存在三角形三元组，则返回 1，否则返回 0。
>
> 例如，给定数组 A 使得：
>
> A\[0\] = 10, A\[1\] = 2, A\[2\] = 5, A\[3\] = 1, A\[4\] = 8, A\[5\] = 20 三元组 (0, 2, 4) 是三角形，该函数应返回 1。
>
> 给定数组 A 使得：
>
> A\[0\] = 10，A\[1\] = 50，A\[2\] = 5，A\[3\] = 1
>
> 函数应该返回 0。
>
> 假使，假设：
>
> N 是 \[0..100,000\] 范围内的整数；
>
> 数组 A 的每个元素都是 \[−2,147,483,648..2,147,483,647\] 范围内的整数。

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

int solution(vector &A) { if(A.size()) 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% 的分数。

我得到了所有测试用例，除了一个：

极端算术溢出1

溢出测试，3 个 MAXINT

我假设这个案例有一些像这样的输入：

[2147483647、2147483647、2147483647]

所以我将它添加到自定义测试用例中，当它显然应该是 1 时，结果却是 0。

我也试过[1900000000, 1900000000, 1900000000]，答案还是0。

但是，[1000000000, 1000000000, 1000000000] 是正确的，答案为 1。

谁能告诉我为什么会出现这个结果？

非常感激。

原文由 toshism 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我的 Java 解决方案具有 ¹⁰⁰⁄₁₀₀ 和 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 + Y > Z ，我们可以简单地检查等效语句 if X > Z - Y （简单的数学不是吗？）。或者，您可以始终使用 long 但这将是一个更糟糕的解决方案内存明智。

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

干杯

原文由 Slobodan Antonijević 发布，翻译遵循 CC BY-SA 4.0 许可协议