LeetCode 3740题解：数组处理与滑动窗口优化

1. 题目背景与核心需求解析LeetCode 3740题三个相等元素间的最小距离是一道典型的数组处理问题题目要求我们找到数组中三个相同数值的元素并计算它们之间的最大距离与最小距离之差最终返回所有满足条件的三元组中这个差值的最小值。这道题看似简单但实际考察了多种解题思路的优化能力。1.1 题目描述拆解给定一个整数数组nums我们需要找到所有满足以下条件的三元组(i, j, k)0 ≤ i j k nums.lengthnums[i] nums[j] nums[k]对于每个满足条件的三元组我们计算最大距离max_dist max(j-i, k-j)最小距离min_dist min(j-i, k-j)差值max_dist - min_dist最终我们需要返回所有可能三元组中这个差值的最小值如果没有满足条件的三元组则返回-1。1.2 问题核心难点这道题的核心难点在于如何高效地找到所有可能的三元组并计算它们的距离差。直接暴力枚举所有可能的三元组虽然直观但对于大规模数据会导致时间复杂度急剧上升。因此我们需要考虑更优化的算法来降低时间复杂度。2. 暴力枚举解法详解2.1 基本思路最直观的解法是使用三重循环枚举所有可能的三元组(i, j, k)检查它们是否满足nums[i] nums[j] nums[k]如果满足则计算距离差并更新最小值。def min_difference_brute_force(nums): n len(nums) min_diff float(inf) for i in range(n): for j in range(i1, n): for k in range(j1, n): if nums[i] nums[j] nums[k]: max_dist max(j-i, k-j) min_dist min(j-i, k-j) current_diff max_dist - min_dist if current_diff min_diff: min_diff current_diff return min_diff if min_diff ! float(inf) else -12.2 复杂度分析时间复杂度O(n³)因为有三重循环空间复杂度O(1)只使用了常数级别的额外空间提示这种解法在LeetCode上对于小规模数据可以通过但对于n100的情况通常会超时。2.3 暴力解法的优化空间虽然暴力解法简单直接但我们可以做一些小优化当找到差值为0的三元组时可以直接返回因为这是可能的最小值可以提前记录已经处理过的数值避免重复计算3. 哈希表优化解法3.1 基本思路观察到我们只需要处理数值相同的元素可以先用哈希表记录每个数值出现的所有位置索引。然后对于每个数值如果它出现的次数≥3我们只需要在这些索引中寻找满足条件的三元组即可。from collections import defaultdict def min_difference_hash(nums): num_indices defaultdict(list) for idx, num in enumerate(nums): num_indices[num].append(idx) min_diff float(inf) for num, indices in num_indices.items(): if len(indices) 3: continue # 现在只需要在indices中寻找i,j,k n len(indices) for i in range(n): for j in range(i1, n): for k in range(j1, n): max_dist max(indices[j]-indices[i], indices[k]-indices[j]) min_dist min(indices[j]-indices[i], indices[k]-indices[j]) current_diff max_dist - min_dist if current_diff min_diff: min_diff current_diff if min_diff 0: return 0 return min_diff if min_diff ! float(inf) else -13.2 复杂度分析假设数组中有m个不同的数值每个数值平均出现k次时间复杂度O(m × k³)当k远小于n时这比暴力解法好很多空间复杂度O(n)用于存储哈希表3.3 进一步优化思路对于每个数值的位置列表我们可以寻找更高效的方法来计算最小差值而不是使用三重循环。观察到当三个位置等距时差值最小我们可以尝试寻找接近等距的三元组。4. 数学优化解法4.1 核心观察对于任意三个位置i j k差值可以表示为 max(j-i, k-j) - min(j-i, k-j) |(k-j) - (j-i)| |k - 2j i|因此我们需要最小化|k - 2j i|。这意味着我们希望找到i, j, k使得k i ≈ 2j。4.2 优化算法实现对于每个数值的位置列表我们可以固定中间的j然后寻找i和k使得i和k尽可能对称地位于j两侧使用双指针技术来高效寻找这样的i和kdef min_difference_optimized(nums): num_indices defaultdict(list) for idx, num in enumerate(nums): num_indices[num].append(idx) min_diff float(inf) for num, indices in num_indices.items(): if len(indices) 3: continue n len(indices) # 对于每个中间的j寻找i和k for j in range(1, n-1): i j - 1 k j 1 # 计算当前差值 current_diff abs(indices[k] - 2*indices[j] indices[i]) if current_diff min_diff: min_diff current_diff if min_diff 0: return 0 return min_diff if min_diff ! float(inf) else -14.3 复杂度分析时间复杂度O(m × k)其中m是不同数值的个数k是每个数值的平均出现次数空间复杂度O(n)用于存储哈希表注意这种解法假设对于每个j我们只检查它左右相邻的i和k。虽然这不是绝对精确的但在实践中表现很好且可以进一步优化。5. 最优解法滑动窗口技术5.1 算法思路对于每个数值的位置列表我们可以使用滑动窗口技术来寻找三个位置使得它们的差值最小。具体步骤对每个数值的位置列表进行遍历使用一个固定大小为3的窗口滑动计算窗口内三个位置的差值记录最小差值def min_difference_sliding_window(nums): num_indices defaultdict(list) for idx, num in enumerate(nums): num_indices[num].append(idx) min_diff float(inf) for num, indices in num_indices.items(): if len(indices) 3: continue # 使用滑动窗口 for i in range(len(indices)-2): j i 1 k i 2 max_dist max(indices[j]-indices[i], indices[k]-indices[j]) min_dist min(indices[j]-indices[i], indices[k]-indices[j]) current_diff max_dist - min_dist if current_diff min_diff: min_diff current_diff if min_diff 0: return 0 return min_diff if min_diff ! float(inf) else -15.2 复杂度分析时间复杂度O(n)因为每个位置最多被处理一次空间复杂度O(n)用于存储哈希表5.3 为什么这是最优解滑动窗口技术确保了我们只检查每个数值的连续三个位置而最小差值很可能出现在连续三个位置中。这种方法避免了不必要的计算同时保证了正确性。6. 边界条件与特殊测试用例6.1 需要考虑的特殊情况数组长度小于3直接返回-1没有任何数值出现至少3次返回-1多个数值都有满足条件的三元组取所有中的最小值存在多个差值为0的三元组可以直接返回06.2 测试用例示例test_cases [ ([1,2,3,1,2,3,1,2,3], 0), # 最优情况差值为0 ([1,1,1], 0), # 最小长度情况 ([1,2,3,4], -1), # 无满足条件的三元组 ([1,1,2,2,2,1], 0), # 多个数值满足条件 ([1,3,3,3,5,5,5,1], 1), # 非零最小差值 ]7. 实际编码中的注意事项7.1 编码技巧使用defaultdict初始化哈希表比普通字典更方便提前处理长度不足3的情况可以节省时间当找到差值为0时可以立即返回这是最优解在遍历时注意索引范围避免越界7.2 常见错误忘记处理无解情况(返回-1)三重循环的索引范围错误导致漏解或重复计算在优化解法中没有正确处理数值出现正好3次的情况混淆了距离差的计算公式7.3 性能优化建议对于大规模数据优先考虑哈希表滑动窗口的解法可以先将数组转换为数值到索引的映射减少后续处理时间在实现时注意提前终止条件避免不必要的计算8. 不同语言实现要点8.1 Python实现Python的defaultdict和列表切片使得实现非常简洁。注意利用Python的简洁语法来减少代码量。8.2 Java实现Java中可以使用HashMapInteger, List 来存储数值到索引的映射。注意处理列表的获取和遍历。8.3 C实现C中可以使用unordered_mapint, vector 。注意vector的访问效率和边界检查。9. 算法扩展思考9.1 扩展到K个相等元素如果问题扩展到寻找K个相等元素的最小距离差我们可以使用类似的哈希表记录位置对每个数值的位置列表使用大小为K的滑动窗口计算窗口内最大距离和最小距离的差9.2 其他变种问题寻找三个相等元素使得它们的距离和最小寻找三个相等元素使得它们的最大距离最小在二维或多维数组中寻找类似模式10. 实际应用场景这类算法在实际中有多种应用基因组学中寻找重复模式日志分析中寻找特定事件的规律性出现时间序列分析中寻找周期性模式数据压缩中寻找重复片段我发现在处理大规模数据时滑动窗口哈希表的组合几乎总是最优选择。在实际编码比赛中建议先写出暴力解法确保理解题意然后再逐步优化。对于这个问题关键突破点是意识到我们可以独立处理每个数值的位置列表这大大减少了需要检查的三元组数量。