"""
存在重复元素 II
"""
from typing import List


class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        """
        基础暴力破解,超出时间限制
        :param nums:
        :param k:
        :return:
        """
        for i, i_val in enumerate(nums):
            for j, j_val in enumerate(nums):
                if i != j and i_val == j_val and abs(i - j) <= k:
                    return True
        return False

    def containsNearbyDuplicate1(self, nums: List[int], k: int) -> bool:
        """
        字典的使用
        :param nums:
        :param k:
        :return:
        """
        num_dict = {}
        for i, num in enumerate(nums):
            # 关键判断
            if num in num_dict and i - num_dict.get(num) <= k:
                return True
            else:
                num_dict[num] = i
        return False


if __name__ == '__main__':
    root = Solution().containsNearbyDuplicate1([1, 2, 3, 1], 3)
    print(root)