Medium

题目描述

给定一个整数数组 nums。

如果 nums[i] == nums[j] == nums[k]，那么由 3 个不同下标组成的元组 (i, j, 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 <= 10^5
  • 1 <= nums[i] <= n

解题思路

这道题的关键在于理解距离公式和寻找最优三元组。

核心观察：

  1. 距离公式 abs(i - j) + abs(j - k) + abs(k - i) 可以简化。对于三个有序的下标 p < q < r，距离等于 2 * (r - p)
  2. 要形成好元组，相同的数字必须至少出现 3 次
  3. 为了最小化距离，我们需要找到相同数字的三个下标，使得最大下标与最小下标的差值最小

算法思路：

  1. 使用哈希表记录每个数字出现的所有下标位置
  2. 对于每个至少出现 3 次的数字，遍历其所有下标组合
  3. 由于下标是按顺序记录的，我们只需要考虑每三个连续的下标，这样能保证 r - p 最小
  4. 计算所有可能组合的距离，返回最小值

时间复杂度优化： 由于我们只需要考虑连续的三个下标，对于有 k 个下标的数字，只需要检查 k-2 个三元组，而不是 C(k,3) 个。

代码实现

class Solution {
public:
    int minimumDistance(vector<int>& nums) {
        unordered_map<int, vector<int>> positions;
        
        // 记录每个数字出现的位置
        for (int i = 0; i < nums.size(); i++) {
            positions[nums[i]].push_back(i);
        }
        
        int minDistance = INT_MAX;
        bool found = false;
        
        // 遍历每个数字
        for (auto& [num, pos] : positions) {
            if (pos.size() < 3) continue;
            
            // 检查每三个连续的位置
            for (int i = 0; i <= (int)pos.size() - 3; i++) {
                int p = pos[i], q = pos[i + 1], r = pos[i + 2];
                int distance = 2 * (r - p);
                minDistance = min(minDistance, distance);
                found = true;
            }
        }
        
        return found ? minDistance : -1;
    }
};

class Solution:
    def minimumDistance(self, nums: List[int]) -> int:
        from collections import defaultdict
        
        positions = defaultdict(list)
        
        # 记录每个数字出现的位置
        for i, num in enumerate(nums):
            positions[num].append(i)
        
        min_distance = float('inf')
        found = False
        
        # 遍历每个数字
        for num, pos in positions.items():
            if len(pos) < 3:
                continue
            
            # 检查每三个连续的位置
            for i in range(len(pos) - 2):
                p, q, r = pos[i], pos[i + 1], pos[i + 2]
                distance = 2 * (r - p)
                min_distance = min(min_distance, distance)
                found = True
        
        return min_distance if found else -1

public class Solution {
    public int MinimumDistance(int[] nums) {
        var positions = new Dictionary<int, List<int>>();
        
        // 记录每个数字出现的位置
        for (int i = 0; i < nums.Length; i++) {
            if (!positions.ContainsKey(nums[i])) {
                positions[nums[i]] = new List<int>();
            }
            positions[nums[i]].Add(i);
        }
        
        int minDistance = int.MaxValue;
        bool found = false;
        
        // 遍历每个数字
        foreach (var kvp in positions) {
            var pos = kvp.Value;
            if (pos.Count < 3) continue;
            
            // 检查每三个连续的位置
            for (int i = 0; i <= pos.Count - 3; i++) {
                int p = pos[i], q = pos[i + 1], r = pos[i + 2];
                int distance = 2 * (r - p);
                minDistance = Math.Min(minDistance, distance);
                found = true;
            }
        }
        
        return found ? minDistance : -1;
    }
}

var minimumDistance = function(nums) {
    const positions = new Map();
    
    // 记录每个数字出现的位置
    for (let i = 0; i < nums.length; i++) {
        if (!positions.has(nums[i])) {
            positions.set(nums[i], []);
        }
        positions.get(nums[i]).push(i);
    }
    
    let minDistance = Infinity;
    let found = false;
    
    // 遍历每个数字
    for (const [num, pos] of positions) {
        if (pos.length < 3) continue;
        
        // 检查每三个连续的位置
        for (let i = 0; i <= pos.length - 3; i++) {
            const p = pos[i], q = pos[i + 1], r = pos[i + 2];
            const distance = 2 * (r - p);
            minDistance = Math.min(minDistance, distance);
            found = true;
        }
    }
    
    return found ? minDistance : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是数组长度。需要遍历数组一次记录位置，然后对每个数字的位置列表进行线性扫描，总体时间复杂度为线性
空间复杂度O(n)，最坏情况下需要存储所有元素的位置信息