查找排序的阵列中的所有对（X，Y），使X + Y＆LT; ž [英] Find all pairs (x, y) in a sorted array so that x + y < z

问题描述

这是一个面试问题。给定一个排序整数数组并数z发现对阵列中的所有对（X，Y），使X + Y＆其中; ž。能不能为O做的更好（N ^ 2）？

This is an interview question. Given a sorted integer array and number z find all pairs (x, y) in the array so that x + y < z. Can it be done better than O(n^2)?

P.S。我知道，我们可以找到所有对（X，Y | X + Y = = Z）。在O（N）

P.S. I know that we can find all pairs (x, y | x + y == z) in O(N).

推荐答案

您不能一定能找到所有这些对在为O（n ² ）时，因为有可能是为O（n ² ）对具有这种属性值。在一般情况下，一个算法不能采取比它产生的值的数目，以运行任何的时间更少。

You cannot necessarily find all such pairs in O(n²) time, because there might be O(n²) pairs of values that have this property. In general, an algorithm can't take any less time to run than the number of values that it produces.

希望这有助于！

这篇关于查找排序的阵列中的所有对（X，Y），使X + Y＆LT; ž的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！