偷吃公司产品，通报批评。。

刚看到个贴子，说某公司运营偷吃了自家产品，结果被通报批评了……😂

今天来整一道算法题，名字很温柔，其实一点也不简单——找出数组中所有 K 近邻下标。

👀 看着像是考查滑窗，其实里面还是有些细节坑点的！我刚拿到这题时还觉得没啥技术含量，结果一上手...嗯，我花了比我想象多三倍的时间调试。那我们直接开搞。

题目意思很简单：给你一个数组 nums 和两个整数 key 和 k，让你找出所有满足以下条件的下标 i：

i 是一个下标，要求它左边 k 个数到右边 k 个数范围里，至少有一个等于 key。

说白了就是：你站在某个位置，往左边看 k 步、往右边看 k 步，看有没有一个数字正好等于 key，有的话这个位置就合格。

例子来一个：

nums = [1,2,3,4,2,1,2], key = 2, k = 2

我们要找出所有“视野范围”内含 key=2 的下标。这里范围 = 自己 ±k。

比如：

• i=0，看[0,2] = [1,2,3]，有个2✅
• i=3，看[1,5] = [2,3,4,2,1]，有个2✅
• i=6，看[4,6] = [2,1,2]，也有✅

那这种题，我第一反应是最暴力的方法：每个下标都检查左右2k范围。代码其实也好写👇

public List<Integer> findKDistantIndices(int[] nums, int key, int k){
    List<Integer> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
// 找出当前位置 ±k 范围内有没有 key
int left = Math.max(0, i - k);
int right = Math.min(n - 1, i + k);
for (int j = left; j <= right; j++) {
if (nums[j] == key) {
                res.add(i);
break;
            }
        }
    }
return res;
}

这方法写起来就像初中作文：“我看他，他看我，一切尽在不言中”。

但！你要是数组有10万长度，O(n*k) 就直接爆炸 💣，因为你每个位置都要扫一圈左右邻居。就好像你在地铁里数头发，一边站着一边旋转，转完下一个人继续旋转……

所以我们要优化。

⚡那怎么优化呢？

我灵机一动（真的不是百度的 😅），既然是“key”的位置影响它周围的点，那我干嘛每个点去查有没有 key？

我只要找到所有 key 的位置，然后反着“扩散”给它周围的点打标就行了。

这方法就是：

找所有 key 出现的位置，对每个 key 的位置 p，向 [p-k, p+k] 范围内标记。

再用一个 boolean[] 标记每个位置是否有效，最后扫一遍收集结果。

这就从 O(n*k) 优化成了 O(n)，直接起飞 🚀！

Java 代码来一个优化版本：

public List<Integer> findKDistantIndices(int[] nums, int key, int k){
int n = nums.length;
boolean[] valid = newboolean[n];

for (int i = 0; i < n; i++) {
if (nums[i] == key) {
int left = Math.max(0, i - k);
int right = Math.min(n - 1, i + k);
for (int j = left; j <= right; j++) {
                valid[j] = true;
            }
        }
    }

    List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (valid[i]) res.add(i);
    }

return res;
}

我试了下，10万个数据压进去，没啥压力——性能稳得一批！

这个解法其实是我之前在写某个滑窗题时无意中想到的“反向扩散思路”，就好像你在草坪上撒洒水器，key 是洒水头，它能喷洒自己周围范围的草地。只要草地被洒到，它就是绿色的（也就是合格的下标）。

如果你还是习惯正向思考，那就是“对每个点看周围有没有水源”，但这个太浪费，效率低。洒水喷头直接出动就好了。

最后一个优化细节，如果 key 很稀疏，你可以先用 List<Integer> 把所有 key 下标记录下来，然后对每个下标扩散，代码可以再抽出一层封装函数，这里就不多写了。

这题暴力可以做，但效率差，优化思路是反向扩散打标法，性能能提升一个量级，确实可以说是“草根逆袭”。

感兴趣的朋友可以自己测测，把数组长度放到 100000，看是否还能稳住。实战项目里遇到滑窗搜索、热区识别、热点传播分析，其实都能用到这个思路