我目前正在为课堂编写这个编码问题.
给定n不同值的排序数组以及目标值T,O(n)及时确定数组中是否存在两个不同的值T.(例如,如果阵列包含3,5,6,7,和9和T = 14,那么你写应该返回方法true,因为5+9 = 14,它应该返回false为值相同的数组,如果T = 17.)
所以,最初,我刚用嵌套线性搜索方法编写问题,这显然导致O(n^2)运行时建立基线以简化,但是,到目前为止,我只能将其简化为O(n log(n)).我这样做是通过创建一个由差异构成的Target - array[i]新数组,然后使用嵌套在线性上升到新数组的循环中的二进制搜索将新数组与原始数组进行比较.
我不是要求答案,而是提示在哪里寻找简化我的代码.我觉得这个数组排序的事实很重要,O(n)但不知道如何去做.
谢谢你的时间!