219. 存在重复元素 II 好

219. 存在重复元素 II

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

//哈希表+滑动窗口
func containsNearbyDuplicate(nums []int, k int) bool {
    hash_m := make(map[int]int)
    for i, v := range nums {
        if _, ok := hash_m[v]; ok && (i - hash_m[v] <= k) {
            return true
        }
        hash_m[v] = i
    }
    return false
}

//好理解一点
func containsNearbyDuplicate(nums []int, k int) bool {
    hash_m := make(map[int]int)                 // 记录窗口的查找表
    for i := 0; i < len(nums); i++ {
        if _, ok := hash_m[nums[i]]; ok {          // 在窗口中找到这个元素
            return true
        }
                                               // 否则说明新的数与窗口中任意数都不重复
        hash_m[nums[i]] = i                     // 将新的数添加到窗口中
        if len(hash_m) == k+1 {                 // 判断这个窗口大小,保持滑动窗口中最多有k个元素
            delete(hash_m, nums[i-k])           // 保持先进先出，删除这个窗口最左侧的数据
        }
    }
    return false                                // 循环结束后没有返回true即没有找到满足条件
}

//暴力比较，有大量重复，On^2，O1

func containsNearbyDuplicate(nums []int, k int) bool {
    for i:=0; i<len(nums)-1; i++ {
        for _,x := range nums[i+1:Min(i+1+k,len(nums))] { // 依次比较该元素后面的 k 个元素是否相等。超过数组长度的部分不比较。
            if nums[i] == x {
                return true
            }
        }
    }
    return false
}

func Min(a,b int) int {
    if a<b {
        return a
    }
    return b
}