(15)Go查找表配合滑动窗口求存在重复元素

方法1：查找表
// 时间复杂度O(n)
// 空间复杂度O(n)
func containsNearbyDuplicate(nums []int, k int) bool {
    // val为i+k,后续如果索引j能取出值并且j<=i+k,则为true
    m := make(map[int]int)

    for i, v := range nums {
        // ok这一步不能省,因为首个元素索引为0,i<=j这一步成立
        // 索引相差不超过k
        if j, ok := m[v]; ok {
            if i <= j {
                return true
            }
        }
        m[v] = i + k
    }
    return false
}

方法2：查找表配合滑动窗口
维持1个长度为k的滑动窗口，窗口内若有不同索引的值相等，则为true
// 时间复杂度O(n)
// 空间复杂度O(k)
func containsNearbyDuplicate2(nums []int, k int) bool {
    m := make(map[int]bool)

    length := len(nums)
    for i := 0; i < length; i++ {
        if m[nums[i]] {
            return true
        }
        m[nums[i]] = true

        // 维持窗口长度
        // 若超出窗口长度,删除最左边元素
        if len(m) > k {
            delete(m, nums[i-k])
        }
    }
    return false
}

提交leetcode，通过