存在重复元素 II（Python）

存在重复元素 II（Python）

一个整数数组 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

思路一：暴力求解，时空复杂度太高，单纯的暴力求解在leetcode会超时。

def repeatnum(nums,k):
    for i in range(len(nums)):
        for j in range(i+1,len(nums)):
            if nums[j] == nums[i] and abs(i-j) <= k:
                return True
    return False

思路二：动态规划、哈希，其实质就是把之前的计算结果保存下来，在后续的计算中使用。python中常用字典实现。

def containsNearbyDuplicate(nums, k):
    dic = {}
    for i in range(len(nums)):
        if nums[i] in dic.keys() and abs(i - dic[nums[i]]) <= k:
            return True
        dic[nums[i]] = i
    return False

思路三：滑动窗口

def windownums(nums,k):
    wid = []  # 滑动窗口
    for i in range(len(nums)):
            if i > k:  # 维护窗口大小  若 i > k，则下标 i − k − 1 处的元素被移出滑动窗口
                wid.pop(0)	# wid.remove(nums[i - k - 1])
            if nums[i] in wid:
                return True
            wid.append(nums[i])
    return False

def containscate(nums, k):
    s = set()
    for i in range(len(nums)):
        if i > k:
            s.remove(nums[i - k - 1])
        if nums[i] in s:
            return True
        s.add(nums[i])
    return False

待研究：使用集合的时间效率比列表好得非常多。