检查n整数数组是否包含3个可形成三角形的数字(即两个数字中的任何一个的总和大于第三个数字的总和).
显然,这可以及时完成O(n).
(显而易见的O(n log n)解决方案是对数组进行排序,所以请不要)
很难想象 N 个数字（其中 N 相当大）使得不存在三角形三元组。但我们会尝试：
考虑一个增长序列，其中每个下一个值都处于极限N[i] = N[i-1] + N[i-2]。无非就是斐波那契数列。近似地，可以将其视为具有黄金比例因子的几何级数（GRf ~= 1.618）。
可见，如果 则N_largest < N_smallest * (GRf**(N-1))肯定会存在一个三角形三元组。由于浮点与整数的关系以及 GRf 的存在，该定义相当模糊，这是一个限制，而不是实际的几何因素。不管怎样，仔细实现它会给出一个 O(n) 测试，可以检查是否确实存在三元组。如果没有，那么我们必须进行一些其他测试（仍在思考中）。
编辑：斐波那契思想的直接结论是，对于整数输入（如 Q 中所指定），如果数组的大小大于，则任何log_GRf(MAX_INT)可能的输入都将存在一个保证的解决方案，对于 32 位为 47，对于 64 位为 93位。实际上，我们可以使用输入数组中的最大值来更好地定义它。
这为我们提供了以下算法：
步骤 1) 从输入数据中查找 MAX_VAL ：O(n)
步骤 2) 计算保证解存在的最小数组大小
N_LIMIT = log_base_GRf(MAX_VAL)：：O(1)
步骤 3.1) 如果 N > N_LIMIT ：返回true：O(1)
步骤3.2）否则排序并使用直接方法O(n*log(n))
因为对于较大的 N 值（这是复杂性很重要的唯一情况），它是O(n)（甚至O(1)在 的情况下N > log_base_GRf(MAX_INT)），我们可以说它是O(n)。