1. 问题理解与需求分析
题目要求我们找到一个整数数组中满足特定条件的三元组(i,j,k)，并计算它们之间的最小距离。具体条件如下：
- 三个位置互不相同：i ≠ j ≠ k
- 三个位置的值相等：nums[i] = nums[j] = nums[k]
- 需要计算的是这三个位置之间的最大距离（即max(|i-j|, |i-k|, |j-k|)中的最小值）
这个问题在实际开发中其实有很强的应用场景。比如在日志分析中，我们可能需要找出某个特定错误代码在日志文件中出现的位置，并计算它们之间的间隔距离，以便分析错误发生的频率模式。
2. 暴力解法与优化思路
最直观的解法是三层循环暴力枚举所有可能的三元组：
func minDistance(nums []int) int { minDist := math.MaxInt32 n := len(nums) for i := 0; i < n; i++ { for j := i+1; j < n; j++ { if nums[i] != nums[j] { continue } for k := j+1; k < n; k++ { if nums[j] == nums[k] { dist := max(k-i, max(j-i, k-j)) if dist < minDist { minDist = dist } } } } } if minDist == math.MaxInt32 { return -1 } return minDist } func max(a, b int) int { if a > b { return a } return b }这个解法的时间复杂度是O(n³)，对于大规模数据显然不够高效。我们需要寻找更优的解决方案。
3. 哈希表优化解法
我们可以利用哈希表来记录每个数值出现的所有位置，然后针对每个出现至少3次的数值，计算其位置之间的最小距离：
func minDistance(nums []int) int { numIndices := make(map[int][]int) for i, num := range nums { numIndices[num] = append(numIndices[num], i) } minDist := math.MaxInt32 for _, indices := range numIndices { if len(indices) < 3 { continue } for i := 0; i <= len(indices)-3; i++ { dist := indices[i+2] - indices[i] if dist < minDist { minDist = dist } } } if minDist == math.MaxInt32 { return -1 } return minDist }这个解法的时间复杂度降低到了O(n)，因为我们只需要遍历数组一次构建哈希表，然后对每个数值的位置列表进行线性扫描。
4. 滑动窗口优化
我们可以进一步优化，使用滑动窗口技术来减少不必要的计算：
func minDistance(nums []int) int { numIndices := make(map[int][]int) for i, num := range nums { numIndices[num] = append(numIndices[num], i) } minDist := math.MaxInt32 for _, indices := range numIndices { n := len(indices) if n < 3 { continue } left := 0 for right := 2; right < n; right++ { currentDist := indices[right] - indices[left] if currentDist < minDist { minDist = currentDist } // 尝试移动左指针以寻找更小的窗口 for left < right-1 && indices[right]-indices[left+1] < currentDist { left++ currentDist = indices[right] - indices[left] if currentDist < minDist { minDist = currentDist } } } } if minDist == math.MaxInt32 { return -1 } return minDist }这个版本的滑动窗口算法在最坏情况下仍然是O(n)时间复杂度，但在实际运行中通常会更快，因为它避免了不必要的计算。
5. 边界条件与测试用例
在实现这类算法时，必须考虑各种边界条件：
- 数组中不存在满足条件的三元组
- 数组中只有三个相同元素
- 数组中有多个满足条件的三元组
- 数组中所有元素都相同
- 数组中元素全部不同
对应的测试用例：
func TestMinDistance(t *testing.T) { tests := []struct { name string nums []int want int }{ {"no triplet", []int{1,2,3,4}, -1}, {"exactly three", []int{1,2,1,3,1}, 2}, {"multiple triplets", []int{1,3,3,3,1,1}, 1}, {"all same", []int{5,5,5,5,5}, 2}, {"all different", []int{1,2,3,4,5}, -1}, {"large array", makeLargeArray(), 9997}, } for _, tt := range tests { t.Run(tt.name, func(t *testing.T) { if got := minDistance(tt.nums); got != tt.want { t.Errorf("minDistance() = %v, want %v", got, tt.want) } }) } } func makeLargeArray() []int { arr := make([]int, 10000) for i := range arr { if i == 0 || i == 5000 || i == 9999 { arr[i] = 1 } else { arr[i] = i + 2 } } return arr }6. 性能分析与优化
让我们分析一下不同解法的性能表现：
- 暴力解法：O(n³)时间，O(1)空间
- 哈希表解法：O(n)时间，O(n)空间
- 滑动窗口优化：O(n)时间，O(n)空间（实际运行更快）
对于Go语言实现，我们还可以做一些微优化：
func minDistance(nums []int) int { numIndices := make(map[int][]int, len(nums)/3) // 预分配空间 for i, num := range nums { numIndices[num] = append(numIndices[num], i) } minDist := math.MaxInt32 for _, indices := range numIndices { n := len(indices) if n < 3 { continue } // 对于每个数值，只需要考虑连续三个位置的最小距离 for i := 0; i <= n-3; i++ { dist := indices[i+2] - indices[i] if dist < minDist { minDist = dist // 最小可能距离是2，可以直接返回 if minDist == 2 { return 2 } } } } if minDist == math.MaxInt32 { return -1 } return minDist }这个优化版本在哈希表创建时预分配了空间，并且在找到最小可能距离(2)时提前返回，可以显著提升某些情况下的性能。
7. 实际应用场景扩展
这个问题虽然看起来简单，但其解法可以应用于多种实际场景：
- 日志分析：找出特定错误码在日志中的出现模式
- 基因组学：寻找DNA序列中特定碱基模式的出现位置
- 金融市场：分析某支股票价格在特定价位出现的频率
- 网络安全：检测重复出现的异常访问模式
例如，在日志分析场景中，我们可以这样使用：
func analyzeErrorLogs(logs []LogEntry) map[string]int { errorCodes := make(map[string][]int) for i, entry := range logs { if entry.IsError() { errorCodes[entry.Code] = append(errorCodes[entry.Code], i) } } result := make(map[string]int) for code, indices := range errorCodes { if len(indices) < 3 { continue } minDist := math.MaxInt32 for i := 0; i <= len(indices)-3; i++ { dist := indices[i+2] - indices[i] if dist < minDist { minDist = dist } } result[code] = minDist } return result }8. 类似问题与扩展思考
这个问题可以扩展为更一般的"在数组中寻找重复模式"的问题。一些变体包括：
- 寻找两个相同元素的最小距离
- 寻找k个相同元素的最小距离
- 考虑元素值在一定范围内的情况（可以使用数组代替哈希表）
- 多维数组中的模式查找
对于寻找两个相同元素的最小距离，解法会更简单：
func minDistanceTwo(nums []int) int { lastSeen := make(map[int]int) minDist := math.MaxInt32 for i, num := range nums { if last, ok := lastSeen[num]; ok { dist := i - last if dist < minDist { minDist = dist } } lastSeen[num] = i } if minDist == math.MaxInt32 { return -1 } return minDist }对于k个相同元素的情况，我们可以将哈希表解法泛化：
func minDistanceK(nums []int, k int) int { numIndices := make(map[int][]int) for i, num := range nums { numIndices[num] = append(numIndices[num], i) } minDist := math.MaxInt32 for _, indices := range numIndices { n := len(indices) if n < k { continue } for i := 0; i <= n-k; i++ { dist := indices[i+k-1] - indices[i] if dist < minDist { minDist = dist } } } if minDist == math.MaxInt32 { return -1 } return minDist }9. Go语言实现细节与性能调优
在Go语言实现中，有几个性能优化的关键点：
- 预分配map空间：使用
make(map[int][]int, initialCapacity)可以减少内存分配次数 - 避免不必要的内存分配：对于已知大小的slice，预分配足够容量
- 使用简单数据结构：如果数值范围有限，可以用数组代替map
- 并行处理：对于超大数组，可以分块并行处理
一个优化后的并行版本可能如下：
func minDistanceParallel(nums []int) int { chunkSize := len(nums) / runtime.NumCPU() if chunkSize < 1000 { return minDistance(nums) // 小数组不并行 } var wg sync.WaitGroup results := make(chan int, runtime.NumCPU()) for i := 0; i < len(nums); i += chunkSize { end := i + chunkSize if end > len(nums) { end = len(nums) } wg.Add(1) go func(chunk []int) { defer wg.Done() localMin := math.MaxInt32 numIndices := make(map[int][]int) for idx, num := range chunk { numIndices[num] = append(numIndices[num], idx) } for _, indices := range numIndices { if len(indices) < 3 { continue } for i := 0; i <= len(indices)-3; i++ { dist := indices[i+2] - indices[i] if dist < localMin { localMin = dist } } } results <- localMin }(nums[i:end]) } go func() { wg.Wait() close(results) }() globalMin := math.MaxInt32 for localMin := range results { if localMin < globalMin { globalMin = localMin } } if globalMin == math.MaxInt32 { return -1 } return globalMin }10. 算法正确性证明
为了确保我们的解法是正确的，让我们进行简单的证明：
- 暴力解法：显然正确，因为它检查了所有可能的三元组组合
- 哈希表解法：
- 将相同数值的位置收集到一起，确保我们只检查有效的三元组
- 对于每个数值的位置列表，我们只需要检查连续三个位置的组合，因为这是获得最小距离的唯一可能
- 因此不会漏掉任何可能的最小距离组合
- 滑动窗口优化：
- 维护一个窗口保证其中有至少三个相同元素
- 移动窗口时总是尝试缩小窗口大小，因此不会错过更小的距离
- 当窗口不能再缩小时，移动右指针寻找新的可能组合
这个问题的解法展示了如何通过合理的预处理（哈希表）将O(n³)的问题转化为O(n)的问题，是算法优化中的一个典型例子。
