当前位置：首页 > news >正文

LeetCode 3740：三个相等元素间的最小距离超详细题解

news 2026/7/31 11:45:30

LeetCode 3740：三个相等元素间的最小距离超详细题解

LeetCode 3740. 三个相等元素之间的最小距离 1【暴力枚举+数学优化+哈希表优化】超详细题解

题目描述

给你一个整数数组nums。

如果满足nums[i] == nums[j] == nums[k]，且(i, j, k)是3 个不同下标，那么三元组(i, j, k)被称为有效三元组。

有效三元组的距离被定义为abs(i - j) + abs(j - k) + abs(k - i)。

返回有效三元组的最小可能距离。如果不存在有效三元组，返回-1。

解题思路

1. 数学公式化简（核心优化）

首先对距离公式进行化简，这是本题最关键的一步：

设三个下标满足a < b < c

距离公式：

∣a−b∣+∣b−c∣+∣c−a∣|a-b| + |b-c| + |c-a|∣a−b∣+∣b−c∣+∣c−a∣

化简后：

(b−a)+(c−b)+(c−a)=2∗(c−a)(b-a) + (c-b) + (c-a) = 2*(c - a)(b−a)+(c−b)+(c−a)=2∗(c−a)

✅结论：三个数的距离 =2 × (最大下标 - 最小下标)

中间下标不影响结果！这一结论对所有优化思路均适用。

2. 算法思路（两种实现）

方法一：暴力枚举（O(n³)，适合小数据量）

三重循环枚举：遍历所有i < j < k的组合，确保三个下标互不相同；
判断有效性：检查nums[i] == nums[j] == nums[k]，确认是有效三元组；
计算距离：使用化简公式2*(k-i)，避免冗余计算；
记录最小值：遍历完成后返回最小距离，若无有效三元组则返回-1。

方法二：哈希表优化（O(n²)，适合更大数据量）

核心思路：利用哈希表分组，减少无效枚举，将时间复杂度从 O(n³) 降至 O(n²)。

分组存储：用哈希表（字典）记录每个数字对应的所有下标，key 为数组元素值，value 为该元素出现的所有下标组成的列表；
筛选有效分组：仅保留下标列表长度 ≥3 的分组（只有这类分组才可能存在有效三元组）；
两两枚举求最小距离：对每个有效分组，遍历所有下标对(a, c)（确保a < c），由于中间下标 b 必然存在（列表长度 ≥3），直接用公式2*(c - a)计算距离，记录该分组的最小距离；
全局求最小：汇总所有有效分组的最小距离，取全局最小值，无有效分组则返回-1。

优化原理：同一数字的下标集中存储，避免遍历无关数字的组合，减少大量无效循环（例如数字 1 对应下标 [0,2,3]，仅需遍历 (0,2)、(0,3)、(2,3) 三对，无需参与其他数字的枚举）。

3. 复杂度分析（两种方法对比）

算法方法	时间复杂度	空间复杂度	适用场景
暴力枚举	O(n3)O(n^3)O(n3)	O(1)O(1)O(1)	n≤100n \le 100n≤100，小数据量、面试手写快速实现
哈希表优化	O(n2)O(n^2)O(n2)	O(n)O(n)O(n)	n≥100n \ge 100n≥100，大数据量、追求更高效率
说明：本题提示中n≤100n \le 100n≤100，两种方法均能轻松通过；但当n≥1000n \ge 1000n≥1000时，O(n³) 会超时，此时哈希表优化版本的优势凸显。

AC 代码（两种版本）

版本一：暴力枚举版本（O(n³)）

from typing import List class Solution: def minimumDistance(self, nums: List[int]) -> int: n = len(nums) min_dist = float('inf') # 枚举所有 i < j < k 的组合，确保下标互不相同 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]: # 利用化简公式计算距离，无需复杂绝对值运算 current = 2 * (k - i) if current < min_dist: min_dist = current # 若未找到有效三元组，返回 -1，否则返回最小距离 return min_dist if min_dist != float('inf') else -1

版本二：哈希表优化版本（O(n²)）

from typing import List from collections import defaultdict class Solution: def minimumDistance(self, nums: List[int]) -> int: # 哈希表：key = 数组元素，value = 该元素出现的所有下标列表 num_indices = defaultdict(list) n = len(nums) min_dist = float('inf') # 1. 遍历数组，填充哈希表，分组存储下标 for idx, num in enumerate(nums): num_indices[num].append(idx) # 2. 遍历每个有效分组（下标列表长度 ≥3） for num, indices in num_indices.items(): m = len(indices) if m < 3: continue # 不足3个下标，无法构成有效三元组，跳过 # 3. 两两枚举下标对 (a, c)，a < c，计算距离 2*(c - a) # 优化：无需遍历所有两两组合，只要找到同组内最接近的两个下标（a,c），就能得到该组最小距离 for a in range(m): # 只需要遍历 a 后面的下标 c（a< c），避免重复计算 for c in range(a + 2, m): # c ≥ a+2，确保中间有下标 b，满足 a < b < c current = 2 * (indices[c] - indices[a]) if current < min_dist: min_dist = current # 4. 返回结果：无有效三元组则返回 -1 return min_dist if min_dist != float('inf') else -1

代码解释（分版本说明）

版本一：暴力枚举代码解释

初始化：min_dist设为无穷大（float(‘inf’)），用于记录最小距离，初始值确保任何有效距离都能覆盖它；
三重循环：通过i range(n)、j range(i+1, n)、k range(j+1, n)，严格保证i < j < k，避免下标重复；
有效判断：只有nums[i] == nums[j] == nums[k]时，才视为有效三元组，进行距离计算；
公式计算：直接使用化简后的2*(k-i)，省略原始公式的绝对值运算，提升效率且避免计算错误；
结果返回：若min_dist仍为无穷大，说明无有效三元组，返回-1；否则返回记录的最小距离。

版本二：哈希表优化代码解释

哈希表初始化：使用defaultdict(list)构建哈希表，避免手动判断 key 是否存在，简化代码；
分组存储下标：遍历数组，将每个元素的下标存入对应 key 的列表中，实现“同值下标分组”；
筛选有效分组：仅处理下标列表长度 ≥3 的分组，直接跳过无法构成有效三元组的分组，减少无效运算；
两两枚举优化：c range(a + 2, m)是关键优化——确保a和c之间至少有一个下标b（满足a < b < c），避免无效的下标对；同时，同组内下标已排序，无需额外排序，直接计算距离；
全局最小距离：遍历所有有效分组，更新全局最小距离，最终返回结果，逻辑与暴力版本一致。