为何该算法的时间复杂度为O(N)而非O(N²)？

先看你给出的代码：

int j = 0;
for (int i = 0; i < N; i++) {
    while ((j < N - 1) && (A[i] - A[j] > D))
        j++;
    if (A[i] - A[j] == D) return 1;
}

你觉得时间复杂度是O(N²)，核心误区是误以为每次外层循环时，内层while的j都会从0开始重新遍历N次，但实际上j的变化是单向递增的——它只会往大了走，永远不会被重置为0或者更小的数值。

具体来说：

• j的初始值是0，整个程序运行过程中，j最多只会从0递增到N-1，总递增次数最多是N次。
• 外层for循环执行N次，但内层while循环的总迭代次数加起来不会超过N次，因为j每递增一次就离上限近一步，不会重复遍历之前的位置。

把外层循环的N次操作，加上内层while的总N次操作，总的时间复杂度就是O(N)，而不是O(N²)。

内容的提问来源于stack exchange，提问作者Resistances in Parallel