219_简单_存在重复元素2

219 存在重复元素II 简单

https://leetcode.cn/problems/contains-duplicate-ii/

算法1：利用map保存索引

// data 2020/01/01
// map
func containsNearbyDuplicate(nums []int, k int) bool {
  m := make(map[int]int)
  for index, v := range nums {
    if j, ok := m[v]; ok && index - j <= k {
      return true
    }
    m[v] = index
  }
  return false
}
// date 2022/09/07
// 优化版本：只保留需要个数的索引
func containsNearbyDuplicate(nums []int, k int) bool {
    set := make(map[int]int, k)
    for idx, v := range nums {
        if o, ok := set[v]; ok && idx - o <= k {
            return true
        }
        set[v] = idx
        if idx >= k {
            delete(set, nums[idx-k])
        }
    }
    return false
}

算法2：双指针

// data 2020/02/02
// two points
func containNearbyDuplicate(nums []int, k int) bool {
  i, j, n := 0, 0, len(nums)
  for i < n {
    j = i + 1
    for j - i <= k && j < n{
      if nums[i] == nums[j] {return true}
      j++
    }
    i++
  }
  return false
}

算法3：滑动窗口

func containsNearbyDuplicate(nums []int, k int) bool {
    queue := make([]int, 0, k)
    for _, v := range nums {
        if checkQueue(queue, v) {
            return true
        }
        queue = append(queue, v)
        if len(queue) > k {
            queue = queue[1:]
        }
    }
    return false
}

func checkQueue(nums []int, n int) bool {
    for _, v := range nums {
        if v == n {
            return true
        }
    }
    return false
}