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

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 后面的下标 ca c避免重复计算 for c in range(a 2, m): # c ≥ a2确保中间有下标 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(i1, n)、k range(j1, 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避免无效的下标对同时同组内下标已排序无需额外排序直接计算距离全局最小距离遍历所有有效分组更新全局最小距离最终返回结果逻辑与暴力版本一致。测试案例验证两种版本均适用案例 1输入[1,2,1,1,3]哈希表分组{1: [0,2,3], 2: [1], 3: [4]}仅 1 的分组有效有效下标对(0,2) → 2*(2-0)4无中间下标跳过、(0,3) → 2*(3-0)6、(2,3) → 2*(3-2)2无中间下标跳过最小距离为 6 ✅ 输出 6案例 2输入[1,1,2,3,2,1,2]哈希表分组{1: [0,1,5], 2: [2,4,6], 3: [3]}1 和 2 的分组有效1 的分组有效下标对(0,5) → 10、(1,5) → 82 的分组有效下标对(2,6) → 8全局最小距离为 8 ✅ 输出 8案例 3输入[1]哈希表分组{1: [0]}无有效分组输出 -1 ✅总结本题核心考点数学公式化简能力核心直接决定计算效率避免冗余运算枚举逻辑的边界处理确保下标互不相同有效三元组的判定哈希表的应用分组优化降低时间复杂度体现空间换时间的思想。补充说明暴力版本适合面试手写代码简洁、逻辑直观、不易出错适配本题小数据量要求哈希表优化版本适合大数据量场景通过空间换时间将时间复杂度从 O(n³) 降至 O(n²)体现算法优化思维两种版本均基于“距离公式化简”的核心结论可见数学推导在算法题中的重要性。