找到 K 个最接近的元素(LeetCode 658)
哪些公司问过
答案要点
- 结果是长度为 k 的连续子数组,只需确定左端点,范围 [0, n−k]
- 二分左端点:若 x − arr[mid] > arr[mid+k] − x 则 left = mid+1,否则 right = mid
- 二分定位后双指针向两边扩展,距离相等优先取较小值
- 复杂度:二分左边界 O(log(n−k) + k),二分加扩展 O(log n + k)
- 边界:x 在数组范围之外、指针越界、比较时慎用绝对值
易错点
- 二分右边界设成 n−1,导致 arr[mid+k] 越界
- 距离相等时没按题意优先取较小元素
- 整个数组按距离排序取前 k 个,O(n log n) 偏高且没用上有序性
面试官常见追问
- 为什么二分比较时不用绝对值?
- 数组无序时怎么做?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。