编程高手请进~~

来源：百度知道 编辑：UC知道 时间：2024/05/20 05:03:45
请给出一个运行时间为@（n lg n）的算法，使之能在给定一个由n个证书构成的集合S和另一个整数x时，判断出S中是否存在有两个其和等于x的元素~~

谢谢~~

用数组记录证书的每一个元素值，这里我用a。
先进行快排，再枚举起始点i（从第一个到第n-1个），二分查找在[i+1,n]之间找x-a[i]，找到了则输出有，所有点都没找到则输出没有。
快排O(NLog2N)
枚举O(N)*二分查找O(Log2N)=O(NLog2N)
所以总的时间复杂度为O(NLog2N)。