? 🤔 新手做題思路：

? 第1步：理解題目

? - 找距離x最近的k個數
- 數組已排序
- 返回結果也要排序（升序）
- 距離相同時，選擇較小的數

? 第2步：關鍵insight

? - 數組已排序 → 考慮二分查找
- 最近的k個數一定是連續的k個數 → 考慮滑動窗口/雙指針
- 只需要找到這個連續區間的起始位置

數組排序和二分查找有關 ，注意滑動窗口不用排序

指定的子串長度和滑動窗口有關

? 第3步：核心思想

? 最近的k個數字一定形成一個長度為k的連續子數組，問題轉化為：
在所有長度為k的子數組中，找到距離x總和最小的那個

● 💡 解題方法（從簡單到優化）：

? 方法1：暴力法（新手先理解這個）

? def findClosestElements_brute(arr, k, x):# 計算每個元素與x的距離，然后排序distances = []for num in arr:distances.append((abs(num - x), num))# 按距離排序，距離相同時按值排序distances.sort(key=lambda item: (item[0], item[1]))# 取前k個元素result = [item[1] for item in distances[:k]]# 返回排序結果return sorted(result)

? 方法2：雙指針法（推薦理解）

? def findClosestElements_two_pointers(arr, k, x):left, right = 0, len(arr) - 1# 收縮到k個元素while right - left >= k:# 比較左右邊界哪個離x更遠，移除更遠的if abs(arr[left] - x) > abs(arr[right] - x):left += 1elif abs(arr[left] - x) < abs(arr[right] - x):right -= 1else:# 距離相同，移除更大的數if arr[left] > arr[right]:left += 1else:right -= 1return arr[left:right + 1]

? 方法3：二分查找（最優解）

? def findClosestElements_binary(arr, k, x):# 二分查找最佳起始位置left, right = 0, len(arr) - kwhile left < right:mid = (left + right) // 2# 比較mid位置和mid+k位置哪個更適合作為起點# 如果x離右邊界更近，說明最佳區間應該右移if x - arr[mid] > arr[mid + k] - x:left = mid + 1else:right = midreturn arr[left:left + k]

? 🔍 詳細解析雙指針法（最容易理解）：

? 核心思想：

? - 初始時：左指針=0，右指針=n-1（包含所有元素）
- 目標：縮小到恰好k個元素
- 策略：每次移除距離x最遠的邊界元素

? 手動模擬：

? arr = [1,2,3,4,5], k = 4, x = 3

? 初始: left=0, right=4, 區間=[1,2,3,4,5] (5個元素)
比較: |1-3|=2 vs |5-3|=2，距離相等，移除較大的5
結果: left=0, right=3, 區間=[1,2,3,4] (4個元素) ?

? 完整代碼實現：

● def findClosestElements(arr, k, x):
"""
推薦的雙指針解法
時間復雜度: O(n)
空間復雜度: O(1)
"""
left, right = 0, len(arr) - 1

? ? ? # 收縮窗口直到剩下k個元素
while right - left + 1 > k:
# 計算左右邊界與x的距離
left_dist = abs(arr[left] - x)
right_dist = abs(arr[right] - x)

? ? ? ? ? if left_dist > right_dist:
# 左邊更遠，移除左邊
left += 1
elif left_dist < right_dist:
# 右邊更遠，移除右邊
right -= 1
else:
# 距離相等，移除數值更大的（題目要求）
if arr[left] > arr[right]:
left += 1
else:
right -= 1

? ? ? return arr[left:right + 1]

? # 測試
print(findClosestElements([1,2,3,4,5], 4, 3)) ? ? ?# [1,2,3,4]
print(findClosestElements([1,1,2,3,4,5], 4, -1)) ?# [1,1,2,3]

? 🚀 二分查找優化版（面試加分）：

? def findClosestElements_optimal(arr, k, x):
"""
二分查找最優起始位置
時間復雜度: O(log n)
空間復雜度: O(1)
"""
# 在[0, n-k]范圍內找最佳起始位置
left, right = 0, len(arr) - k

? ? ? while left < right:
mid = (left + right) // 2

? ? ? ? ? # 關鍵判斷：比較mid和mid+k位置
# 如果x更靠近右邊界，說明最優區間應該右移
if x - arr[mid] > arr[mid + k] - x:
left = mid + 1
else:
right = mid

? ? ? return arr[left:left + k]

? 🎯 復雜度對比：

? | 方法 ? | 時間復雜度 ? ? ?| 空間復雜度 | 難度 ?|
|------|------------|-------|-----|
| 暴力法 ?| O(n log n) | O(n) ?| ? ? |
| 雙指針 ?| O(n) ? ? ? | O(1) ?| ?? ?|
| 二分查找 | O(log n) ? | O(1) ?| ??? |

? 📝 考試建議：

? 優先掌握雙指針法：
- 思路清晰，容易理解
- 代碼簡潔，不容易出錯
- 時間復雜度已經很好了

? 二分查找法作為加分項：
- 面試時展現算法功底
- 但邏輯相對復雜，容易出錯

? ★ Insight ─────────────────────────────────────
這道題的關鍵洞察是：最近的k個元素必然是連續的。因為如果不連續，中間跳過的元素肯定比端點的某個元素更接近x，這與最優性矛盾。基于這個洞察，問題就轉化為尋找最
優的連續k元素子數組，可以用雙指針或二分查找來高效求解。
─────────────────────────────────────────────────