2200. 找出数组中的所有 K 近邻下标

🟢   🔖  数组 双指针  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums and two integers key and k. A k-distant index is an index i of nums for which there exists at least one index j such that |i - j| <= k and nums[j] == key.

Return a list of all k-distant indices sorted in increasing order.

Example 1:

Input: nums = [3,4,9,1,3,9,5], key = 9, k = 1

Output: [1,2,3,4,5,6]

Explanation: Here, nums[2] == key and nums[5] == key.

• For index 0, |0 - 2| > k and |0 - 5| > k, so there is no j where |0 - j| <= k and nums[j] == key. Thus, 0 is not a k-distant index.
• For index 1, |1 - 2| <= k and nums[2] == key, so 1 is a k-distant index.
• For index 2, |2 - 2| <= k and nums[2] == key, so 2 is a k-distant index.
• For index 3, |3 - 2| <= k and nums[2] == key, so 3 is a k-distant index.
• For index 4, |4 - 5| <= k and nums[5] == key, so 4 is a k-distant index.
• For index 5, |5 - 5| <= k and nums[5] == key, so 5 is a k-distant index.
• For index 6, |6 - 5| <= k and nums[5] == key, so 6 is a k-distant index.

Thus, we return [1,2,3,4,5,6] which is sorted in increasing order.

Example 2:

Input: nums = [2,2,2,2,2], key = 2, k = 2

Output: [0,1,2,3,4]

Explanation: For all indices i in nums, there exists some index j such that |i - j| <= k and nums[j] == key, so every index is a k-distant index.

Hence, we return [0,1,2,3,4].

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• key is an integer from the array nums.
• 1 <= k <= nums.length

题目大意

给你一个下标从 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

解题思路

1. 初始化双指针：

   • i：用于遍历 nums，找到所有值等于 key 的下标。
   • j：用于生成满足条件的下标 j。

2. 遍历 nums 寻找目标值：

   • 指针 i 找到满足 nums[i] === key 的下标。
   • 如果当前值不等于 key，继续移动 i。

3. 调整指针 j 的位置：

   • 如果 |i - j| > k，说明当前 j 不符合条件，将其移动到满足条件的位置。
   • 当 |i - j| <= k，逐一将所有符合条件的下标 j 加入结果数组 res。

4. 继续移动 i：

   • 继续寻找下一个满足 nums[i] === key 的位置。

复杂度分析

• 时间复杂度：O(n)

  • 指针 i 遍历数组一次，时间复杂度为 O(n)。
  • 指针 j 在每个满足 nums[i] === key 的范围内移动，总的移动次数不会超过 O(n)。
  • 总时间复杂度为 O(n)。

• 空间复杂度：O(n)，结果数组 res 使用额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} key
 * @param {number} k
 * @return {number[]}
 */
var findKDistantIndices = function (nums, key, k) {
	const n = nums.length;
	let res = [];
	let i = 0; // 遍历数组的指针
	let j = 0; // 满足条件的下标指针

	while (i < n) {
		// 找到 nums[i] === key 的位置
		while (i < n && nums[i] !== key) {
			i++;
		}

		// 调整 j，使其满足 |i - j| <= k
		while (Math.abs(i - j) > k) {
			j++;
		}

		// 将满足条件的下标加入结果数组
		while (Math.abs(i - j) <= k && i < n && j < n) {
			res.push(j);
			j++;
		}

		// 移动到下一个可能的 key 的位置
		i++;
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
1	两数之和	[✓]	数组 哈希表	🟢	🀄️ 🔗
243	最短单词距离 🔒		数组 字符串	🟢	🀄️ 🔗
2817	限制条件下元素之间的最小绝对差		数组 二分查找 有序集合	🟠	🀄️ 🔗