219_contains_duplicate_ii

219. 存在重复元素 II 简单

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

代码参考：

package main

import "fmt"

func main() {
    fmt.Println(containsNearbyDuplicate([]int{1, 0, 1, 1}, 1)) // true
}

// 查找还是哈希表比较 ok
func containsNearbyDuplicate(nums []int, k int) bool {
    duplicates := make(map[int][]int)
    for i, num := range nums {
        duplicates[num] = append(duplicates[num], i) // 把索引存起来
    }

    for _, dups := range duplicates {
        if len(dups) <= 1 {
            continue
        }
        for i := len(dups) - 1; i > 0; i-- {
            if dups[i]-dups[i-1] <= k { // 计算彼此的间隔
                return true
            }
        }
    }
    return false
}