【第 284 场周赛】6031. 找出数组中的所有 K 近邻下标-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

给你一个下标从 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 <= 1000
1 <= nums[i] <= 1000
key 是数组 nums 中的一个整数
1 <= k <= nums.length

二、思路分析

读懂题目描述后，我第一感觉就是寻找规律。所谓 K 近邻下标 是指 nums 中的一个下标 i ，并满足至少存在一个下标 j 使得 |i - j| <= k 且 nums[j] == key ，也就是说我需要找到数组中值为 key 的元素，获取这个元素的下标，以这个下标为中点、以 k 为步长左右扩展，扩展后的区间范围内的所有下标就是我们要找的 K 近邻下标。

需要注意的是：

这个扩展区间最多扩展到数组的边界，也就是 [0, nums.length] ，因此如果 nums 数组第一个元素值为 key 且 k >= 1 ，就需要处理这个扩展区间的左边界了，同样右边界也是如此。
题目给的 nums 数组中可能会出现多个值为 key，因此创建一个 arr 数组，将值为 key 的元素下标存进去。
题目要求以列表形式返回按 递增顺序 排序的所有 K 近邻下标，由于是从左往右遍历数组，本身就保持了递增顺序，因此无需理会这个条件。
由于可能有多个值为 key 的元素，因此也就可能会有多个扩展区间，这些扩展区间就有可能会有交点，为了不使结果数组有重复元素，可以使用 Set 去重。

解题流程如下：

创建 arr 数组和 res 数组，arr 用来存放值为 key 的元素，res 用来存放所有 K 近邻下标。
遍历 nums 数组，找到其中值为 key 的元素，将该元素的下标 push 进 arr 数组。
遍历 arr 数组，确定以当前元素为中点、以 k 为步长的扩展区间，注意处理区间范围。
将区间范围内的值（相当于 nums 数组的元素下标） push 进 res 数组。
对 res 数组进行去重即可完成题目。

三、AC 代码

/**
 * @param {number[]} nums
 * @param {number} key
 * @param {number} k
 * @return {number[]}
 */
var findKDistantIndices = function(nums, key, k) {
    let arr = [], res = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === key) {
            arr.push(i);
        }
    }
    for (let i = 0; i < arr.length; i++) {
        let num = arr[i] - k >= 0 ? arr[i] - k : 0;
        while (num <= arr[i] + k && num < nums.length) {
            res.push(num++);
        }
    }
    return Array.from(new Set(res));
};
复制代码