解决方案

方法一：排序

思路

不失一般性的，我们假设三角形的边长满足 $$a \leq b \leq c$$ 。那么这三条边组成三角形的面积非零的充分必要条件是 $$a + b > c$$ 。

再假设我们已经知道 $$c$$ 的长度了，我们没有理由不从数组中选择尽可能大的 $$a$$ 与 $$b$$ 。因为当且仅当 $$a + b > c$$ 的时候，它们才能组成一个三角形。

算法

基于这种想法，一个简单的算法就呼之欲出：排序数组。对于数组内任意的 $$c$$ ，我们选择满足条件的最大的 $$a \leq b \leq c$$ ，也就是大到小排序，位于 $$c$$ 后面的两个元素。 从大到小枚举 $$c$$ ，如果能组成三角形的话，我们就返回答案。

复杂度分析

• 时间复杂度： $$O(N \log N)$$ ，其中 $$N$$ 是数组 A 的长度。
• 空间复杂度： $$O(1)$$ 。