> For the complete documentation index, see [llms.txt](https://leetcodebook-1.gitbook.io/top-interview-150/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcodebook-1.gitbook.io/top-interview-150/hash-table/contains-duplicate-ii.md).

# 存在重复元素 II

题目链接: <https://leetcode.cn/problems/contains-duplicate-ii>

## 解题思路一：

1. 判断数组中每个元素与其之后的k个元素是否有相同数字
2. 若有，则返回true

```go
func containsNearbyDuplicate(nums []int, k int) bool {
    for i:=0;i<len(nums);i++{
        for j:=i+1;j<=i+k&&j<len(nums);j++{
            if nums[i]==nums[j]{
                return true
            }
        }
    }
    return false
}
```

## 复杂度分析一

* **时间复杂度：** 时间复杂度是 $$O(n^2)$$
* **空间复杂度：** 空间复杂度是 $$O(1)$$

## 解题思路二：

1. 遍历每个元素，用map记录每个元素出现的位置
2. 当第二次出现元素时，判断当前元素与之前最后一次出现的元素的位置距离是否小于k，若是则返回true

```go
func containsNearbyDuplicate(nums []int, k int) bool {
    pos := map[int]int{}
    for i, num := range nums {
        if p, ok := pos[num]; ok && i-p <= k {
            return true
        }
        pos[num] = i
    }
    return false
}
```

## 复杂度分析二

* **时间复杂度：** 时间复杂度是 $$O(n)$$
* **空间复杂度：** 空间复杂度是 $$O(n)$$