Easy

题目描述

给你一个整数数组 nums。

一个由 3 个不同下标组成的元组 (i, j, k) 是好的，当且仅当 nums[i] == nums[j] == nums[k]。

好元组的距离定义为 abs(i - j) + abs(j - k) + abs(k - i)，其中 abs(x) 表示 x 的绝对值。

返回一个整数，表示好元组的最小可能距离。如果不存在好元组，返回 -1。

示例 1：

输入：nums = [1,2,1,1,3]
输出：6
解释：
最小距离由好元组 (0, 2, 3) 实现。
(0, 2, 3) 是一个好元组，因为 nums[0] == nums[2] == nums[3] == 1。
它的距离是 abs(0 - 2) + abs(2 - 3) + abs(3 - 0) = 2 + 1 + 3 = 6。

示例 2：

输入：nums = [1,1,2,3,2,1,2]
输出：8
解释：
最小距离由好元组 (2, 4, 6) 实现。
(2, 4, 6) 是一个好元组，因为 nums[2] == nums[4] == nums[6] == 2。
它的距离是 abs(2 - 4) + abs(4 - 6) + abs(6 - 2) = 2 + 2 + 4 = 8。

示例 3：

输入：nums = [1]
输出：-1
解释：
不存在好元组。因此，答案是 -1。

提示：

  • 1 <= n == nums.length <= 100
  • 1 <= nums[i] <= n

解题思路

这道题要求找到三个相等元素的最小距离。我们需要理解距离的计算公式：对于三个下标 i < j < k，距离为 abs(i - j) + abs(j - k) + abs(k - i) = (j - i) + (k - j) + (k - i) = 2 * (k - i)。

因此，对于任意三个相等元素的下标，距离实际上就是 2 * (最大下标 - 最小下标)。

解法思路：

  1. 暴力枚举法：由于数组长度最大为 100，我们可以直接枚举所有可能的三元组 (i, j, k)，检查是否为好元组，并计算距离。

  2. 优化方法：对于每个值，先收集所有出现的下标，然后枚举任意三个下标计算最小距离。由于距离公式简化为 2 * (max_index - min_index)，我们只需要找到每个值的最小和最大下标即可。

  3. 最优解法：使用哈希表记录每个值的所有出现位置，对于每个值，如果出现次数 >= 3，则枚举所有可能的三个位置组合来计算最小距离。

代码实现

class Solution {
public:
    int minimumDistance(vector<int>& nums) {
        int n = nums.size();
        int minDist = INT_MAX;
        bool found = false;
        
        // 暴力枚举所有可能的三元组
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] == nums[j] && nums[j] == nums[k]) {
                        found = true;
                        int dist = abs(i - j) + abs(j - k) + abs(k - i);
                        minDist = min(minDist, dist);
                    }
                }
            }
        }
        
        return found ? minDist : -1;
    }
};

class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        n = len(nums)
        min_dist = float('inf')
        found = False
        
        # 暴力枚举所有可能的三元组
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] == nums[j] == nums[k]:
                        found = True
                        dist = abs(i - j) + abs(j - k) + abs(k - i)
                        min_dist = min(min_dist, dist)
        
        return min_dist if found else -1

public class Solution {
    public int MinimumDistance(int[] nums) {
        int n = nums.Length;
        int minDist = int.MaxValue;
        bool found = false;
        
        // 暴力枚举所有可能的三元组
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] == nums[j] && nums[j] == nums[k]) {
                        found = true;
                        int dist = Math.Abs(i - j) + Math.Abs(j - k) + Math.Abs(k - i);
                        minDist = Math.Min(minDist, dist);
                    }
                }
            }
        }
        
        return found ? minDist : -1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumDistance = function(nums) {
    const n = nums.length;
    let minDistance = Infinity;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] === nums[j] && nums[j] === nums[k]) {
                    const distance = Math.abs(i - j) + Math.abs(j - k) + Math.abs(k - i);
                    minDistance = Math.min(minDistance, distance);
                }
            }
        }
    }
    
    return minDistance === Infinity ? -1 : minDistance;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)需要枚举所有可能的三元组，共有 C(n,3) = O(n³) 种组合
空间复杂度O(1)只使用了常数级别的额外空间