LeetCode 2200: Find All K-Distant Indices in an Array ·

基本資料
#

難易度: easy 第一次嘗試：2026-01-04

提交紀錄：Accepted（暴力）→ Wrong Answer → Accepted ×2

解題思路
#

每個 nums[j] == key 的位置，會讓 [j - k, j + k] 裡的 index 都成為答案。把這些區間聯集起來、依序輸出。

依序掃過每個 key 的位置，區間的起點只會越來越右，所以用一個指針 next_start 記住「已經輸出到哪裡」：下一個區間從 max(next_start, j - k) 開始輸出，就不會重複。

我的嘗試
#

第一版：暴力
#

對每個 index 檢查所有 key 的位置，有一個距離 <= k 就加入。正確，時間 O(n · key 的數量)。

第二版：區間重疊時重複輸出
#

改成對每個 key 輸出 [j - k, j + k]，但沒有處理區間重疊。例如 nums = [2, 3, 2, 1, 1, 2, 1, 2]、key = 2、k = 3：每個 key 的區間都互相重疊，同一個 index 被輸出好幾次，答案變成 [0, 1, 2, 3, 0, 1, 2, 3, 4, 5, ...]。

加上一個記錄上一個區間結尾的指針就 AC 了。

正確解法
#

class Solution:
    def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
        n = len(nums)
        res = []
        next_start = 0                         # 下一個還沒輸出的 index
        for j, x in enumerate(nums):
            if x == key:
                start = max(next_start, j - k)
                end = min(n - 1, j + k)
                res.extend(range(start, end + 1))
                next_start = end + 1
        return res