33t*_*ted 2 algorithm big-o asymptotic-complexity
我们有一个带有m个正整数的数组A,这是一个算法
如果A中存在三元组(x,y,z),则返回true,使得A [x] + A [y] + A [z] = 200
否则返回false.数组中的数字是不同的,运行时间必须是O(n).
我想出了O(n ^ 3).关于如何用O(n)实现这一点的任何想法？
由于元素是唯一的,因此归结为在O(n)中预处理数组以过滤冗余元素 - 大于200(它们都不在三元组中).
比,你有一个大小不超过200的数组.
检查此数组中的所有三元组O(200^3)=O(1)(尽管可以在常量方面更有效地完成).
所以,这将是 O(n) U O(200^3) = O(n)