数组中的数字是否包含有效三角形的边
检查 n 个整数数组是否包含 3 个可以形成三角形的数字（即任何两个数字之和大于第三个数字）。
显然，这可以在 O(n) 时间内完成。
（明显的 O(n log n) 解决方案是对数组进行排序，所以请不要这样做）
Check if an array of n integers contains 3 numbers which can form a triangle (i.e. the sum of any of the two numbers is bigger than the third).
Apparently, this can be done in O(n) time.
(the obvious O(n log n) solution is to sort the array so please don't)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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 : return
true:O(1)步骤 3.2) else 排序并使用直接方法
O(n*log(n))因为对于N 的值很大（这是复杂性很重要的唯一情况），它是
O(n)（甚至在N > 的情况下是)，我们可以说它是O(1); log_base_GRf(MAX_INT)O(n)。It's difficult to imagine N numbers (where N is moderately large) so that there is no triangle triplet. But we'll try:
Consider a growing sequence, where each next value is at the limit
N[i] = N[i-1] + N[i-2]. It's nothing else than Fibonacci sequence. Approximately, it can be seen as a geometric progression with the factor of golden ratio (GRf ~= 1.618).It can be seen that if the
N_largest < N_smallest * (GRf**(N-1))then there sure will be a triangle triplet. This definition is quite fuzzy because of floating point versus integer and because of GRf, that is a limit and not an actual geometric factor. Anyway, carefully implemented it will give an O(n) test that can check if the there is sure a triplet. If not, then we have to perform some other tests (still thinking).EDIT: A direct conclusion from fibonacci idea is that for integer input (as specified in Q) there will exist a garanteed solution for any possible input if the size of array will be larger than
log_GRf(MAX_INT), and this is 47 for 32 bits or 93 for 64 bits. Actually, we can use the largest value from the input array to define it better.This gives us a following algorithm:
Step 1) Find MAX_VAL from input data :
O(n)Step 2) Compute the minimum array size that would guarantee the existence of the solution:
N_LIMIT = log_base_GRf(MAX_VAL):O(1)Step 3.1) if N > N_LIMIT : return
true:O(1)Step 3.2) else sort and use direct method
O(n*log(n))Because for large values of N (and it's the only case when the complexity matters) it is
O(n)(or evenO(1)in cases whenN > log_base_GRf(MAX_INT)), we can say it'sO(n).