给定一个数字数组，找出所有满足给定条件的三元组。
条件:a[i] < a[j] < a[k]其中 I < j < k .
有没有可能在O(n)时间内解决这个问题？
这不是家庭作业!!!
最佳答案
输出的大小(最坏情况)是复杂性的下限。
因为可能有 O(n^3) 个这样的三元组，所以复杂度不可能是 O(n)。
例如，如果数组从低到高排序，您将有 n 个选择 3 个这样的三元组，其顺序为 n^3。
如果问题涉及找到三胞胎的数量，这是我看到的最有效的解决方案:
关于arrays - 是否有可能在 O(n) 时间内找到给定数组中的所有三元组？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21532143/