查找排序列表中具有特定差异的数字

给定列表已排序，您可以在O（n）时间中通过列表运行两个指针。基本上是这样的：

index1 = 0index2 = 0while index2 < size(array):    if array[index2] - array[index1] == K:        print both numbers and exit    if array[index2] - array[index1] < K:        index2++;    else        index1++;

换句话说，如果数字之间的差异太小，则增加较高的数字（使差异较大），否则增加较低的数字（使差异减小）。

您可以在以下Python程序中看到这一点：

lst = [1,2,3,4,5,6,7,50,100,120,121,122,123,130,199,299,399]diff = 7ix1 = 0ix2 = 0while ix2 < len (lst):    print "Comparing [%d]=%d against [%d]=%d"%(ix1,lst[ix1],ix2,lst[ix2])    if lst[ix2] - lst[ix1] == diff:        print lst[ix1], lst[ix2]        break    if lst[ix2] - lst[ix1] < diff:        ix2 = ix2 + 1    else:        ix1 = ix1 + 1

输出：

Comparing [0]=1 against [0]=1Comparing [0]=1 against [1]=2Comparing [0]=1 against [2]=3Comparing [0]=1 against [3]=4Comparing [0]=1 against [4]=5Comparing [0]=1 against [5]=6Comparing [0]=1 against [6]=7Comparing [0]=1 against [7]=50Comparing [1]=2 against [7]=50Comparing [2]=3 against [7]=50Comparing [3]=4 against [7]=50Comparing [4]=5 against [7]=50Comparing [5]=6 against [7]=50Comparing [6]=7 against [7]=50Comparing [7]=50 against [7]=50Comparing [7]=50 against [8]=100Comparing [8]=100 against [8]=100Comparing [8]=100 against [9]=120Comparing [9]=120 against [9]=120Comparing [9]=120 against [10]=121Comparing [9]=120 against [11]=122Comparing [9]=120 against [12]=123Comparing [9]=120 against [13]=130Comparing [10]=121 against [13]=130Comparing [11]=122 against [13]=130Comparing [12]=123 against [13]=130123 130