携手创作，一起成长！这是我参与「日新方案 8 月更文应战」的第16天，点击查看活动概况

标题

给你一个整数数组nums 和一个整数k，判别数组中是否存在两个 不同的索引i和j，满意 nums[i] == nums[j] 且 abs(i - j) <= k。假如存在，回来 true；否则，回来 false。

示例 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

方法一：哈希表

思路及解法

从左到右遍历数组 $nums$，当遍历到下标 $i$ 时，假如存在下标 $j<i$ 使得 $nums[i]=nums[j]$，则当 $i-j\le k$ 时即找到了两个符合要求的下标 $j$ 和 $i$。

假如在下标 $i$ 之前存在多个元素都和 $nums[i]$ 持平，为了判别是否存在满意 $nums[i]=nums[j]$ 且 $i-j\le k$ 的下标 $j$，应该在这些元素中寻觅下标最大的元素，将最大下标记为 $j$，判别 $i-j\le k$ 是否建立。

假如 $i-j\le k$，则找到了两个符合要求的下标 $j$ 和 $i$；假如 $i-j>ki-j>k$，则在下标 $i$ 之前不存在任何元素满意与 $nums[i]$ 持平且下标差的绝对值不超越 $k$，理由如下。

假设存在下标 $j\prime$ 满意 j′<j<ij’ < j < ij′<j<i 且 $nums[j\prime ]=nums[j]=nums[i]$，则 i−j′>i−j>i−ji – j’ > i – j>i−ji−j′>i−j>i−j，由于 $i-j>k$，因而必有 i−j′>ki – j’ > ki−j′>k。

因而，当遍历到下标 $i$ 时，假如在下标 $i$ 之前存在与 $nums[i]$ 持平的元素，应该在这些元素中寻觅最大的下标 $j$，判别 $i-j\le k$ 是否建立。

能够运用哈希表记录每个元素的最大下标。从左到右遍历数组 $nums$，当遍历到下标 $i$ 时，进行如下操作：

1. 假如哈希表中现已存在和 $nums[i]$ 持平的元素且该元素在哈希表中记录的下标 $j$ 满意 $i-j\le k$，回来 $true$；

2. 将 $nums[i]$ 和下标 $i$ 存入哈希表，此时 $i$ 是 $nums[i]$ 的最大下标。

上述两步操作的次序不能改动，由于当遍历到下标 $i$ 时，只能在下标 $i$ 之前的元素中寻觅与当时元素持平的元素及该元素的最大下标。

当遍历结束时，假如没有遇到两个持平元素的下标差的绝对值不超越 $k$，回来 $false$。

代码

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var map: [Int:Int] = [:]
        for i in 0..<nums.count {
            let num = nums[i]
            if nil != map[num] && (i - (map[num] ?? 0)) <= k {
                return true
            }
            map[num] = i
        }
        return false
    }
}

复杂度剖析

• 时间复杂度：$O(n)$，其间 $n$ 是数组 $nums$ 的长度。需求遍历数组一次，对于每个元素，哈希表的操作时间都是 $O(1)$。

• 空间复杂度：$O(n)$，其间 $n$ 是数组 $nums$ 的长度。需求运用哈希表记录每个元素的最大下标，哈希表中的元素个数不会超越 $n$。

方法二：滑动窗口

思路及解法

考虑数组 nums 中的每个长度不超越 k + 1 的滑动窗口，同一个滑动窗口中的恣意两个下标差的绝对值不超越 k。假如存在一个滑动窗口，其间有重复元素，则存在两个不同的下标 i 和 j 满意 nums[i]=nums[j] 且 ∣i−j∣≤k。假如一切滑动窗口中都没有重复元素，则不存在符合要求的下标。因而，只要遍历每个滑动窗口，判别滑动窗口中是否有重复元素即可。

假如一个滑动窗口的结束下标是 i，则该滑动窗口的开端下标是 max(0,i−k)。能够运用哈希调集存储滑动窗口中的元素。从左到右遍历数组 nums，当遍历到下标 i 时，具体操作如下：

1. 假如 i>k，则下标 i−k−1 处的元素被移出滑动窗口，因而将 nums[i−k−1] 从哈希调集中删去；
2. 判别 nums[i] 是否在哈希调集中，假如在哈希调集中则在同一个滑动窗口中有重复元素，回来 true，假如不在哈希调集中则将其加入哈希调集。

当遍历结束时，假如一切滑动窗口中都没有重复元素，回来 false。

代码

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var set = Set<Int>()
        for i in 0..<nums.count {
            if i > k {
                set.remove(nums[i - k - 1])
            }
            if set.contains(nums[i]) {
                return true
            }
            set.insert(nums[i])
        }
        return false
    }
}

复杂度剖析

• 时间复杂度：$O(n)$，其间 $n$ 是数组 $nums$ 的长度。需求遍历数组一次，对于每个元素，哈希调集的操作时间都是 $O(1)$。

• 空间复杂度：$O(k)$，其间 $k$ 是判别重复元素时允许的下标差的绝对值的最大值。需求运用哈希调集存储滑动窗口中的元素，恣意时间滑动窗口中的元素个数最多为 $k+1$ 个。