提供一个用 O(nlogn) 执行的算法来解决以下问题

Question

编写一个复杂度为 O(n lg n) 的算法，该算法接收以非递减顺序排列的 n 个实数数组 A 和一个值 val 作为输入。如果存在不同的索引 i 和 j 使得 a[i] + a[j] = val，则算法 returns 为真，否则为假。

我想到了以下伪代码，但意识到它只适用于相邻元素

checkArray(Array A, val)    
if  A.length==2        
if A[0] + A[1] =val
return true;        
else  
return false       
else   
L1 = checkArray (A[0 : n/2],val) 
L2 = checkArray(A[n/2 : n], val)

Answer 1

评论中的提示几乎给出了 O(nlogn) 答案 - 遍历每个元素 a[i]，并对数组进行二进制搜索以查看 val - a[i] 是否存在。我不打算详细介绍这个算法，因为它看起来相当简单。相反，我想阐明 O(n) 解决方案，它可能不是那么明显。

简而言之，O(n) 使用两个指针，从两端向中间移动，不断检查两者之和是否等于 val。如果它们的总和大于 val，我们通过将其指针向左移动一位来减少两者中较大的一个（最右边的指针）。如果它更小，我们通过向右移动它的指针来增加两者中较小的一个。如果两个指针相互传递，我们知道不存在解决方案。

checkArray(Array A, val)
    indexLo = 0
    indexHi = len(A) - 1
    while indexLo <= indexHi
        sum = A[indexLo] + A[indexHi]
        if sum == val
            return True

        if sum < val
            indexLo += 1
        else
            indexHi -= 1
    return False

提供一个用 O(nlogn) 执行的算法来解决以下问题

Providing an algorithm which executes with O(nlogn) to solve the following problem

algorithm

analysis