LeetCode 219. 存在重复元素 II Contains

【题目描述】
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

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

【思路1】
1、暴力解
2、分别判断两个值是否相等且 index绝对值 <= k
3、时间复杂度O(n^2)
4、代码略

【思路2】
1、使用哈希表 [value：index]
2、把数值当做key，index当做value
3、遍历数组，当map[n]有值时，判断abs(map[n]-cur) <= k
4、时间复杂度O(n)
5、空间复杂度O(n)

Swift代码实现:

func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
    var map = [Int:Int]()
    for (i,n) in nums.enumerated() {
        if let tmp = map[n] {
            if abs(tmp-i) <= k {
                return true
            }
        }
        map[n] = i
    }
    return false
}

后续会继续更新文章，也可以关注我的公众号：

个人公号.jpg