class Solution {
    // 배열에서 x에 가장 가까운 k개의 정수
    // T: O(n)
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
		List<Integer> result = new ArrayList<>(k);
        
        // Two Pointer
        int lo = 0, hi = arr.length - 1;
        
        // 구간의 원소의 개수가 K개가 될때까지 절대값을 비교하면서 두 구간의 위치를 변경한다.
		while (hi - lo + 1 > k) {
			if (Math.abs(arr[lo] - x) > Math.abs(arr[hi] - x)) {
				lo++;
			} else {
				hi--;
			}
		}
        
		for (int i = lo; i <= hi; i++) {
			result.add(arr[i]);
		}
        
		return result;
    }
}