LeetCode219：存在重复元素IIContainsDuplicateII

题目：给定一个整数数组和一个整数k，判断数组中是否存在两个不同的下标i和j使得nums[i]=nums[j]，且i和j之差的绝对值至多为k.给定一个整数数组和一个整数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解题思路：遍历数组，维护一个大小为K的滑动窗口，窗口遍历的第i个元素，然后是K个元素组成的数组nums[i,i+K]，找出数组中是否有等于nums[i]的元素唯一可以优化的地方就是滑动窗口的维护，减少这个动态数组中的查找操作有很多方法可以优化数组查找的时间复杂度：暴力破解：直接操作指针比较正在遍历的元素和它后面的K个元素。平衡二叉树：构建平衡二叉树维护滑动窗口哈希集：维护一个长度为K的哈希集，搜索复杂度为O(1)。只有使用hash集合维护滑动窗口，秦策才不会超时HashSet问题解决：Java:classSolution{publicbooleancontainsNearbyDuplicate(int[]nums,intk){HashSetset=newHashSet<>();for(inti=0;ik)set.remove(nums[i-k]);}返回假；}}Python:class解决方案：defcontainsNearbyDuplicate(self,nums:List[int],k:int)->bool:hash_set=set()fori,numinenumerate(nums):ifnuminhash_set:returnTruehash_set.add(num)if(len(hash_set)>k):hash_set.remove(nums[i-k])欢迎关注微..信.公.众..号:爱写Bug