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),但我并没有真正得到它.内循环执行N次,外部也应该N次？是因为j = 0; 在循环之外使它只运行N次？
但即使它只在内循环中运行N次,if语句检查也应该进行N次,这应该将总时间复杂度带到O(n ^ 2)？