能否利用数组中的数值构成三角形

给定一个整数数组，我们需要确定是否有可能利用数组中的数值作为边长，构造出至少一个非退化#Triangle)三角形。换句话说，我们需要找到 3 个能够满足非退化三角形边长条件的数组索引。

示例：

输入：[4, 1, 2]
输出：No 
给定的数组值无法构成三角形

输入：[5, 4, 3, 1, 2]
输出：Yes
可能构成的三角形边长为 2 3 4

推荐练习 构成三角形 立即尝试！

对于非退化三角形，其边长应满足以下约束条件：

A + B > C    并且     
B + C > A    并且
C + A > B
其中 A、B 和 C 是三角形的边长。

我们的任务是从数组中找到任意一个满足上述条件的三元组。

一种简单的解决方案是生成所有三元组，并对每个三元组通过检查上述三个条件来判断它们是否能构成三角形。

一种高效的解决方案是使用排序。首先，我们对数组进行排序，然后遍历一次，检查该数组中三个连续的元素，如果任意一个三元组满足 arr[i] + arr[i+1] > arr[i+2]，那么我们将输出该三元组作为我们的最终结果。

为什么只检查 3 个连续元素就能奏效，而不是尝试排序后数组所有可能的三元组呢？

假设我们位于索引 INLINECODEa398cdb4 处，三个线段分别为 INLINECODEfdc44e71、INLINECODEcb57c9e3 和 INLINECODE33439289，且满足关系 INLINECODEc6761f37。如果它们不能构成非退化三角形，那么长度为 INLINECODE6c473729、INLINECODE9bdd1122 和 INLINECODE588e529e 或者 INLINECODE9941ada0、INLINECODEa6b7c94f 和 INLINECODE60840868 的线段也不能构成非退化三角形。因为在第一种情况下，INLINECODE8c6758ec 和 INLINECODEc0ff057c 的和甚至小于 INLINECODEeb3ef92b 和 INLINECODE47417a05 的和；在第二种情况下，INLINECODE6d8fa2f6 和 INLINECODE1f379b4b 的和必然小于 INLINECODEfb5de7d4。因此，我们不需要尝试所有的组合，只需尝试排序后数组中 3 个连续的索引即可。

下面解决方案的总复杂度为 O(n log n)。辅助空间为 O(1)。

实现：
在练习页面上尝试！

C++


CODEBLOCK_53f678f5


C


CODEBLOCK_34d22e4b


JAVA


“java

// Java program to find if it is possible to form a

// triangle from array values

import java.io.*;

import java.util.Arrays;

class GFG {

// Method prints possible triangle when array values are

// taken as sides

static boolean isPossibleTriangle(int[] arr, int N)

{

// If number of elements are less than 3, then no

// triangle is possible

if (N < 3)

return false;

// first sort the array

Arrays.sort(arr);

// loop for all 3 consecutive triplets

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

// If triplet satisfies triangle condition, break

if (arr[i] + arr[i + 1] > arr[i + 2])