题目链接：https://leetcode.cn/problems/find-k-closest-elements/

题目难度：中等

题意

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

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

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

示例1：

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

示例2：

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

提示：

  • $1 <= k <= arr.length$
  • $1 <= arr.length <= 10^4$
  • arr 按 升序 排列
  • $-10^4 <= arr[i], x <= 10^4$

题解一：双指针

首先遍历数组找到最接近x的元素位置pos，然后以pos向左右两边遍历，找到符合条件的k的元素，最后返回这k个元素的子数组即可。

时间复杂度：$O(n+k)$

其实还可以优化，无需找到pos，直接定义左指针从0开始，右指针从数组末尾开始，相向寻找，知道左右指针所包含的子数组长度为k即可。

C++代码

class Solution {
public:
    bool check(int a,int b,int x){
        if(abs(a-x)<abs(b-x)) return true;
        else if(abs(a-x)==abs(b-x)&&a<b) return true;
        else return false;
    }
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n=arr.size();
        //找到和x最接近的数
        int pos=0;
        for(int i=1;i<n;i++){
            if(check(arr[i],arr[pos],x)) pos=i;
        }
      
        vector<int> ans;ans.push_back(arr[pos]);
        int i=pos-1,j=pos+1,cnt=1;
        // cout<<pos<<endl;
        while(i>=0 && j<n && cnt<k){
            if(check(arr[i],arr[j],x)){
                --i;++cnt;
            }else{
                ++j;++cnt;
            }
        }
        while(i>=0 && cnt<k){
            --i;++cnt;
        }
        while(j<n && cnt<k){
            ++j;++cnt;
        }
        return vector<int>(arr.begin()+i+1,arr.begin()+j);
    }
};

题解二：二分查找

由于最后的结果是连续的区间（即子数组），于是转化为求符合条件的最优区间，进而可以转换为最优区间的左边界即可（因为k确定，即长度确定）

左边界最小取值为：0，最大取值为：arr.size()-k。

然后二分查找其最优结果即可。

具体二分思考参考下面链接：https://leetcode.cn/problems/find-k-closest-elements/solution/pai-chu-fa-shuang-zhi-zhen-er-fen-fa-python-dai-ma/

时间复杂度：$O(logn)$

C++代码

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n=arr.size();
        int l=0,r=n-k;
        while(l<r){
            int mid=(l+r)>>1;
            //尝试从k+1的区间中删除一个元素
            //从而定位最终区间的左边界值
            if(x-arr[mid] > arr[mid+k]-x){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return vector<int>(arr.begin()+l,arr.begin()+l+k);
    }
};