如何在数组中找到最小距离？

Question

输入是排序整数的数组，我必须找到数量| a。[i] - a。[j] |之间的最小距离。和一个给定的数字d。如何找到最小的距离？

distance = ||a.[i]-a.[j]| - d| 

Answer 1

这看起来很容易做线性时间。鉴于一些评论中存在的一些困惑，我可能会错过一些让我的解决方案无用的东西。无论如何，这里我去：

I know this looks much like Java, however it's intended to be pseudocode. 

Array is a, array size is n, array elements are a[0] to a[n-1] 
Target distance is d, assumed non-negative 

i=0; 
j=0; 
solutionI = 0; 
solutionJ = 0; 
minError = d; 

while (j < n) 
{ 
    error = abs(a[j]-a[i]-d) // abs is absolute value 
    if (error < minError) 
    { 
    solutionI = i; 
    solutionJ = j; 
    minError = error; 
    } 

    if (a[j] - a[i] <= d) 
    { 
    // Gap between a[i] and a[j] is too short, increase j to increase gap 
    // Note we also advance j when we have an exact match 
    // This is to keep always j>=i even when d=0 
    j++; 
    } 
    else 
    { 
    // Gap between a[i] and a[j] is too long, increase i to decrease gap 
    i++; 
    } 
} 

Now solutionI and solutionJ mark the closest match to gap d 
Also, minError tells how far we are from target distance d