小胖和三角形的故事。

问题描述

给定若干正数,问其中是否存在三个数可以构成三角形,若存在则输出其周长,否则输出-1。有多组解时求出任一解即可。

分析

若暴力循环则复杂度为$O(n^3)$

猜想将数组排序,若存在连续的三个数可以构成三角形,则返回这三个数的和,否则返回-1。这样算法复杂度为$O(\log n+n)$。

证明:只需证明若排序后不存在连续的三个数可以构成三角形,则不存在任意三个数可以构成三角形。这是显然的。