math - 三角形 : Determine whether a triangle can be built from a given set of edges

Question

我在网上找到了解决以下编码问题的解决方案:

给出了一个由 N 个整数组成的零索引数组 A。如果 0 ≤ P < Q < R < N 并且:

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

例如，考虑数组 A 使得:

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

三元组 (0, 2, 4) 是三角形的。

写一个函数:

 int solution(int A[], int N);

也就是说，给定一个由 N 个整数组成的零索引数组 A，如果该数组存在三角形三元组，则返回 1，否则返回 0。

解决方案是这样的:

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

但是当我们对数组进行排序时，原始索引不再有效，并且在 i 位置的项目可以移动到 j 位置，其中 j>i 或 j

该解决方案假设验证断言(三角形)的值在排序数组中自动相邻。

在示例数组中，如果我们像这样改变:

A[0] = 10 A[1] = 6(替换 2)A[2] = 5
A[3] = 1 A[4] = 8 A[5] = 20
在这里，我们得到了 2 个新的 traingle 10 6 5 和 6 5 8。(和 10 5 8)

我们排序: 1 5 6 8 10 20 --> 这里，原始解 (10,5,8) 值不相邻(没有 traingle)，而是我们有 (5,6,8) 和 (6 8 10)。然后算法返回1。
似乎如果三角形存在，那么至少一个三角形的值将是相邻的，但我没有找到任何证据。

Answer 1

这是我在 Java 中的解决方案。在 Codility 上给我 100% 结果。

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);

        for (int i = 2; i < A.length; i++) {
            long p = A[i - 2]; 
            long q = A[i - 1]; 
            long r = A[i];

            if (p + q <= r) {
                continue;
            } 
            if (r + p <= q) {
                continue;
            } 
            if (q + r <= p) {
                continue;
            } 
            return 1;
        }

        return 0;
    }
}