algorithm - 这个算法能在 O(n) 时间内运行吗？

Question

我正在编写一个算法来确定排序数组中是否有一对整数总和为给定整数。我希望算法在 O(n) 中运行，其中 n 是子数组中整数的数量。

输入是子数组和整数的边界，用于测试总和。输出将是一个 bool 值。

这是我的算法。 k是给定的整数，i和j是子数组的边界。

kPairSumInterval(int k, int i, int j)
         if(i == (j-1))
              sum = A[i] + A[j]
              if(sum == k)
                 found = true;

         kPairSumInterval(k,i+1,j)
         for j down to i
              sum = A[i] + A[j]
              if(sum == k)
                  found = true

        return found

while 循环会影响运行时间还是我们只关注递归的堆栈帧数？如果该算法无法在 O(n) 时间内运行，我将不胜感激一些使其在 O(n) 内运行的建议。

Answer 1

对于排序列表来说足够简单的算法。
假设所有正整数，将索引设置为列表的末尾，将索引设置为列表的开头，并根据总和减少结束索引或增加起始索引。
Python 伪代码:

def kPairSumInterval(k, i, j):
    x, y = i, j-1
    while x < y and A[x] + A[y] != k:
        if A[x] + A[y] > k:
            y -= 1
        else:
            x += 1
    return x < y

仅出于演示目的递归地使用相同的算法，使用 bool 运算，即 True==1 和 False==0:

def kPairSumInterval(k, i, j):
    if i >= j-1:
        return False
    result = A[i] + A[j-1]
    if result == k:
        return True
    return kPairSumInterval(k, i+(result < k), j-(result > k))