victory的博客

长安一片月，万户捣衣声

0%

leetcode | 219.存在重复元素2

发表于 分类于 ， ， ，

219.存在重复元素2

题目描述

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

题目链接

思路

  1. 哈希表
    使用哈希表存储每一个元素的最大下表，在遍历元素的过程中，如果该元素已存在于哈希表中，则判断该元素当前下标减去该元素的最大下标，如果差值小于k，则返回True;
    如果遍历过程中没有找到为相等元素且下标之差小于k的情况，则返回False。
  2. 滑动窗口
    数组 nums 中的每个长度不超过 k+1 的滑动窗口，同一个滑动窗口中的任意两个下标差的绝对值不超过 k。如果存在一个滑动窗口，其中有重复元素，则存在两个不同的下标 i 和 j 满足 nums[i]=nums[j] 且 ∣i−j∣≤k。如果所有滑动窗口中都没有重复元素，则不存在符合要求的下标。因此，只要遍历每个滑动窗口，判断滑动窗口中是否有重复元素即可。

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    class Solution(object):
    	def containsNearbyDuplicate(self, nums, k):
    		"""
    		超出时间限制
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
    		dict1 = dict()
    		for i in range(len(nums)):
    			if nums[i] not in dict1.keys():
    				dict1[nums[i]] = [i]
    			else:
    				dict1[nums[i]].append(i)

    		for key in dict1.keys():
    			for i in range(len(dict1[key])):
    				for j in range(i+1, len(dict1[key])):
    					if abs(dict1[key][i]-dict1[key][j]) <= k:
    						return True
    		else:
    			return False

    	def containsNearbyDuplicate1(self, nums, k):
    		"""超出时间限制"""
    		i = 0
    		while i < len(nums)-1:
    			j = i + 1
    			while j < len(nums):
    				if nums[i] == nums[j] and abs(i-j) <= k:
    					return True
    				j += 1
    			i += 1
    		return False
    	
    	def containsNearbyDuplicate2(self, nums, k):
    		"""哈希表"""
    		pos = {}
    		for i, num in enumerate(nums):
    			if num in pos and i - pos[num] <= k:
    				return True
    			pos[num] = i
    		return False
    	
    	def containsNearbyDuplicate3(self, nums, k):
    		"""集合"""
    		s = set()
    		for i, num in enumerate(nums):
    			if i > k:
    				s.remove(nums[i - k - 1])
    			if num in s:
    				return True
    			s.add(num)
    		return False


    if __name__ == "__main__":
    	slt = Solution()
    	# print(slt.containsNearbyDuplicate1([1, 2, 3, 1], 3))
    	# print(slt.containsNearbyDuplicate1([1, 0, 1, 1], 1))
    	# print(slt.containsNearbyDuplicate1([1, 2, 3, 1, 2, 3], 2))
    	# print(slt.containsNearbyDuplicate1([99, 99], 2))
    	
    	print(slt.containsNearbyDuplicate2([1, 2, 3, 1], 3))
    	print(slt.containsNearbyDuplicate2([1, 0, 1, 1], 1))
    	print(slt.containsNearbyDuplicate2([1, 2, 3, 1, 2, 3], 2))
    	print(slt.containsNearbyDuplicate2([99, 99], 2))