puzzle - 数组中的数字是否包含有效三角形的边

Question

检查 n 的数组是否整数包含 3 个可以形成三角形的数字(即两个数字中任何一个的总和大于第三个)。

显然，这可以在 O(n) 中完成。时间。

(明显的 O(n log n) 解决方案是对数组进行排序，所以请不要)

Answer 1

很难想象 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) else 排序并使用直接方法 O(n*log(n))
因为对于较大的 N 值(这是复杂性很重要的唯一情况)，它是 O(n) (甚至 O(1) 在 N > log_base_GRf(MAX_INT) 的情况下)，我们可以说它是 O(n) .