请教个面试题# JobHunting - 待字闺中
w*n
1 楼
Write a function that is given an array of integers. It should return true
if and only if there are two distinct indices i and j into the array such
that the difference between arr[i] and arr[j] is at most l and the
difference between i and j is at most k.
存在 O(n) 的解法么？我现在能想到的就是maintain一个 l 大小的sorted list 然后
一路扫过去。每次删头和加尾需要log l。然后判断新插入的数和相邻数是否满足 dif
< k。 就是O（n log l）。
if and only if there are two distinct indices i and j into the array such
that the difference between arr[i] and arr[j] is at most l and the
difference between i and j is at most k.
存在 O(n) 的解法么？我现在能想到的就是maintain一个 l 大小的sorted list 然后
一路扫过去。每次删头和加尾需要log l。然后判断新插入的数和相邻数是否满足 dif
< k。 就是O（n log l）。
