ORID35 binary search/sliding win

[658] Find K closest elements 解题报告

算法

用什么算法
Binary search / Sliding Window
为什么用这个算法（那些条件）
这次学到了Sliding window 这个technique，youtube 上面有个视频讲得不错，主要是说这些方法是我们解题的一个技巧，你要学会应用到不同的场景（就是根据条件来判断sliding window 到底合不合适）而不是死记算法。
sliding window 的使用场景就是在一段区间内（怎么有点像二分法里的range？？） 选出符合条件的答案。比如选出一组sum 最接近target的数。这时候就可以用sliding window 了（当然这个不是二分法的sliding window）
这题则是要找每个数距离taget最近的一组数。如果距离一样，那么小的数优先。举个例子，target是3，你要选3个数，数组给的是[1,2,3,4,5] 你发现左右两边距离target一样，但答案应该是[1,2,3] 因为小数优先。

代码实现

有什么要注意的地方
这道题我一开始也是二分法，但我想的是先通过二分法来找到距离target最近的值（其实已经通过了好几个testcase了，但是发现在一组数的时候不行。）我的二分会不小心把距离target为0的数给切掉。当时也耗了很长时间了，所以去看了别人的答案，发现sliding window能很轻松的解决这个问题，因为你在这个window 里面如果mid的距离离target 比mid + k 距离 target 要远，那就说明你的窗口过于左边了，要向右边走。所以 start = mid + 1; 反之 end = mid;
这里是代码

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int start = 0, end = arr.length - k;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (x - arr[mid] > arr[mid + k] - x) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return Arrays.stream(arr, start, start + k).boxed().collect(Collectors.toList());
    }

这里

if (x - arr[mid] > arr[mid + k] - x) {

判断就是我上面说的， 如果目前mid距离target（也就是x）远过 mid + k 到 x 的距离，那就说明你当前的mid 太过左边了。长的应该是这样的
case 3: x - A[mid] > A[mid + k] - x, need to move window go right
-------A[mid]------------------x---A[mid + k]----------

case 4: x - A[mid] > A[mid + k] - x, need to move window go right
-------A[mid]---------------------A[mid + k]----x------

反过来，如果你mid + k 大于 mid 到 x 的距离，长的应该是这样：
case 1: x - A[mid] < A[mid + k] - x, need to move window go left
-------x----A[mid]-----------------A[mid + k]----------

case 2: x - A[mid] < A[mid + k] - x, need to move window go left again
-------A[mid]----x-----------------A[mid + k]----------

这段解释是从这里搬过来的，这位老哥解释的很好。我经常看他的参考答案。

有什么可以优化的地方

时空复杂度分析

Time complexity O(log(N-K))
Space O(K)

相关题目有哪些做过的

跟哪个题目比较像？
这目前头一次接触到sliding window，我觉得这是一个很重要的方法。