1848. 到目标元素的最小距离

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given an integer array nums (0-indexed) and two integers target and start, find an index i such that nums[i] == target and abs(i - start) is minimized. Note that abs(x) is the absolute value of x.

Return abs(i - start).

It is guaranteed that target exists in nums.

Example 1:

Input: nums = [1,2,3,4,5], target = 5, start = 3

Output: 1

Explanation: nums[4] = 5 is the only value equal to target, so the answer is abs(4 - 3) = 1.

Example 2:

Input: nums = [1], target = 1, start = 0

Output: 0

Explanation: nums[0] = 1 is the only value equal to target, so the answer is abs(0 - 0) = 0.

Example 3:

Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0

Output: 0

Explanation: Every value of nums is 1, but nums[0] minimizes abs(i - start), which is abs(0 - 0) = 0.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4
• 0 <= start < nums.length
• target is in nums.

题目大意

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数 target 和 start ，请你找出一个下标 i ，满足 nums[i] == target 且 abs(i - start) 最小化 。注意：abs(x) 表示 x 的绝对值。

返回 abs(i - start) 。

题目数据保证 target 存在于 nums 中。

示例 1：

输入： nums = [1,2,3,4,5], target = 5, start = 3

输出： 1

解释： nums[4] = 5 是唯一一个等于 target 的值，所以答案是 abs(4 - 3) = 1 。

示例 2：

输入： nums = [1], target = 1, start = 0

输出： 0

解释： nums[0] = 1 是唯一一个等于 target 的值，所以答案是 abs(0 - 0) = 0 。

示例 3：

输入： nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0

输出： 0

解释： nums 中的每个值都是 1 ，但 nums[0] 使 abs(i - start) 的结果得以最小化，所以答案是 abs(0 - 0) = 0 。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^4
• 0 <= start < nums.length
• target 存在于 nums 中

解题思路

可以从 start 开始同时向两边扩展，直到找到目标值。

1. 双向遍历：i 用来向左移动，j 用来向右移动。
2. 同时从 start 向左（i--）和向右（j++）移动。
3. 在每一次循环中，先检查 i 是否有效（即是否超出数组范围），如果有效且 nums[i] == target，则更新 res 为从 start 到 i 的距离。
4. 同时，检查 j 是否有效，如果有效且 nums[j] == target，则更新 res 为从 start 到 j 的距离。
5. 提前终止：一旦找到了目标值，计算并返回距离，遍历就可以结束。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度，最多需要遍历数组一遍。
• 空间复杂度：O(1)，只使用了常数空间来存储临时变量。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @param {number} start
 * @return {number}
 */
var getMinDistance = function (nums, target, start) {
	// 双向遍历
	for (let i = start, j = start; i >= 0 || j < nums.length; i--, j++) {
		if (i >= 0 && nums[i] == target) {
			// 向左查找
			return start - i;
		}
		if (j < nums.length && nums[j] == target) {
			// 向右查找
			return j - start;
		}
	}
};