LeetCode 题解工作台
找出数组中的所有 K 近邻下标
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。 K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| 且 nums[j] == key 。 以列表形式返回按 递增顺序 排序的所有 K 近邻下标。 示例 1： 输入： nums …
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 双·指针·invariant
答案摘要
我们在 $[0, n)$ 的范围内枚举下标 ，对于每个下标 ，我们在 $[0, n)$ 的范围内枚举下标 ，如果 $|i - j| \leq k$ 且 $nums[j] = key$，那么 就是一个 K 近邻下标，我们将 加入答案数组中，然后跳出内层循环，枚举下一个下标 。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 双·指针·invariant 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 和两个整数 key 和 k 。K 近邻下标 是 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key 。
以列表形式返回按 递增顺序 排序的所有 K 近邻下标。
示例 1：
输入：nums = [3,4,9,1,3,9,5], key = 9, k = 1 输出：[1,2,3,4,5,6] 解释：因此，nums[2] == key且nums[5] == key。 - 对下标 0 ，|0 - 2| > k且|0 - 5| > k，所以不存在j使得|0 - j| <= k且nums[j] == key。所以 0 不是一个 K 近邻下标。 - 对下标 1 ，|1 - 2| <= k且nums[2] == key，所以 1 是一个 K 近邻下标。 - 对下标 2 ，|2 - 2| <= k且nums[2] == key，所以 2 是一个 K 近邻下标。 - 对下标 3 ，|3 - 2| <= k且nums[2] == key，所以 3 是一个 K 近邻下标。 - 对下标 4 ，|4 - 5| <= k且nums[5] == key，所以 4 是一个 K 近邻下标。 - 对下标 5 ，|5 - 5| <= k且nums[5] == key，所以 5 是一个 K 近邻下标。 - 对下标 6 ，|6 - 5| <= k且nums[5] == key，所以 6 是一个 K 近邻下标。 因此，按递增顺序返回 [1,2,3,4,5,6] 。
示例 2：
输入：nums = [2,2,2,2,2], key = 2, k = 2 输出：[0,1,2,3,4] 解释：对nums的所有下标 i ，总存在某个下标 j 使得|i - j| <= k且nums[j] == key，所以每个下标都是一个 K 近邻下标。 因此，返回 [0,1,2,3,4] 。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 1000key是数组nums中的一个整数1 <= k <= nums.length
解题思路
方法一：枚举
我们在 的范围内枚举下标 ，对于每个下标 ，我们在 的范围内枚举下标 ，如果 且 ，那么 就是一个 K 近邻下标，我们将 加入答案数组中，然后跳出内层循环，枚举下一个下标 。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def findKDistantIndices(self, nums: List[int], key: int, k: int) -> List[int]:
ans = []
n = len(nums)
for i in range(n):
if any(abs(i - j) <= k and nums[j] == key for j in range(n)):
ans.append(i)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each index is scanned once and checked against nearby key positions. Space complexity is O(1) extra beyond the input, as the output list is required by the problem. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if the solution handles multiple key occurrences correctly.
- question_mark
Ask whether the indices list is correctly sorted without extra sorting steps.
- question_mark
Probe handling of edge indices near array boundaries.
常见陷阱
外企场景- error
Failing to include all indices within k distance of multiple key occurrences.
- error
Adding duplicate indices when k ranges overlap for consecutive keys.
- error
Incorrectly handling indices at the start or end of the array.
进阶变体
外企场景- arrow_right_alt
Return k-distant indices in descending order instead of increasing.
- arrow_right_alt
Count the total number of k-distant indices instead of listing them.
- arrow_right_alt
Find indices distant from multiple different keys simultaneously.