一

用bubble sort或selection sort,原本swap()的部分改成比較兩數的差距是否為k

⇒可能會超時

二

1 8 3 9 10, k=1

for i 0 to len(a)

if(a[a[i]])

找到了

a[a[i]+k]=True

a[a[i]-k]=True

i=3 a[i]=9的時候,找到相差為1的兩個數(8,9)

⇒ 這個方法只需要O(n)的time complexity

⇒ 但是題目有限制 0<=Ai<=2³¹-1,陣列大小可能需要(2³¹),

⇒ 很顯然的不能這樣做,可以用hash function來改進

這個方法可以這麼想,我知道你是誰了,可是不知道你在哪裡,存不存在,因此我把你的名字記下來,然後去找你

三

對陣列A排序,宣告兩個變數p=0,q=1

if a[q]-a[p]<k

q+=1

if a[q]-a[p]>k

p+=1

if(p==q)

q+=1

if a[q]-a[p]==k

return true

如果差距比k小,那麼就增加距離

如果差距比k大,那摩就縮小距離

⇒可行的解法, time complexity是O(nlgn)

結論

這裡提供三種思路,除了第三種方法,大家也可以試試看用hash來實現第二種方法,

如果有什麼疑問,歡迎提出來哦