题目名称

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例

输入：arr = [1,2,3,4,5], k = 4, x = 3

输出：[1,2,3,4]

题解

滑动窗口

首先由题意可以先处理一些极端的用例，例如输入的 x 小于数组的最小值，或者大于数组的最大值，这个时候只需要返回数组头部或者尾部的k位元素即可
然后采用滑动窗口的方法，首先定义 left 和 right 两个指针，两个指针的差 right - left 即为窗口的大小，然后移动 right 指针，由于我们已经处理好边界值了，可以得出数组中一定有大于等于 x 的元素，所以我们可以一路将 right 指针移动到第一个大于等于 x 的元素位置，left 指针同步保持与 right 指针相差 k 个大小

接下来通过 left 指针对应元素大小以及 right 指针对应元素大小与 x 差的绝对值进行比较，如果 arr[right] - x >= x - arr[left] 且 right - left < k,则继续移动 right 指针的位置，否则 根据 right - left与k 进行比较来决定是否移动 left和 right 指针

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 var findClosestElements = function(arr, k, x) {
    let length = arr.length
    let left = 0, right = 0
    if(arr[left] >= x) return arr.slice(0, k)
    if(arr[length - 1] <= x) return arr.slice(length - k, length)
    while(right < length) {
        if(arr[right] <= x) {
            if(right - left >= k) {
                left++
            }
            right++
        } else {
            if(arr[right] - x >= x - arr[left]) {
                if(right - left >= k) {
                    break;
                } else {
                    right++
                }
            } else {
                if(right - left >= k) {
                    right++
                    left++
                } else {
                    right++
                }
            }
        }
    }
    return arr.slice(left, right)
};