存在重复元素模块-三道题

存在重复元素

217. 存在重复元素

题目链接：217. 存在重复元素
题目大意：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

注意：（1）1 <= nums.length <= $10^5$；（2）$-10^9$ <= nums[i] <= $10^9$。

示例：

输入：nums = [1,2,3,1]
输出：true输入：nums = [1,2,3,4]
输出：false输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

参考代码：

class Solution:def containsDuplicate(self, nums: List[int]) -> bool:# 取巧return len(set(nums)) != len(nums)'''# hash maphash_map = dict()for num in nums:if num not in hash_map:hash_map[num] = 1else:return Truereturn False''''''# 计数器counter = collections.Counter(nums)for num in nums:if counter[num] > 1:return Truereturn False'''

• （1）取巧办法：
• 时间复杂度：$O(1)$。
• 空间复杂度：$O(n)$，其中 $n$ 是 $nums$ 的长度。
• （2）hash map办法：
• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$
• （3）计数器办法：
• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

219. 存在重复元素 II

题目链接：219. 存在重复元素 II
题目大意：给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

注意：（1）1 <= nums.length <= $10^5$；（2）$-10^9$ <= nums[i] <= $10^9$；（3）0 <= k <= $10^5$。

示例：

输入：nums = [1,2,3,1], k = 3
输出：true输入：nums = [1,0,1,1], k = 1
输出：true输入：nums = [1,2,3,1,2,3], k = 2
输出：false

参考代码：

class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:hash_map = dict()for i,num in enumerate(nums):if num not in hash_map:hash_map[num] = ielse:if i - hash_map[num] <= k:return Truehash_map[num] = ireturn False

• 时间复杂度：$O(n)$，其中 $n$ 是 $nums$ 的长度。
• 空间复杂度：$O(n)$

220. 存在重复元素 III （SortedList+二分）

题目链接：220. 存在重复元素 III
题目大意：给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。

注意：（1）0 <= nums.length <= $2\ast 10^4$；（2）$-2^{31}$ <= nums[i] <= $2^{31}-1$；（3）0 <= k <= $10^4$；（4）0 <= t <= $2^{31}-1$。

示例：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true输入：nums = [1,0,1,1], k = 1, t = 2
输出：true输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

参考代码：

from sortedcontainers import SortedList class Solution:def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:wd  = SortedList()n = len(nums)for i in range(n):# print(wd)if i>k:wd.remove(nums[i-1-k])wd.add(nums[i])idx = bisect.bisect_left(wd,nums[i])if idx>0 and abs(wd[idx]-wd[idx-1])<=t:return Trueif idx<len(wd)-1 and abs(wd[idx+1]-wd[idx])<=t:return Truereturn False

• 时间复杂度：$O(n\log k)$，其中 $n$为数组的长度，TreeSet 基于红黑树，查找和插入都是 $O(\log k)$ 复杂度。
• 空间复杂度：$O(k)$

小结

• 这三道题挺有趣的，之间的关联并不是非常大，不过都用到了哈希表这个容器，是一套不错的练习题，总结记录一下，便于快速查询，加油（23.3.3)。