目录
1. 存在重复元素 Contains Duplicate I
2. 存在重复元素 Contains Duplicate II
3. 存在重复元素 Contains Duplicate III
1. 存在重复元素 Contains Duplicate I
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1] 输出：true
示例 2：
输入：nums = [1,2,3,4] 输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2] 输出：true
提示：
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
代码： 多种方法实现
from typing import List
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return True
return False
def containsDuplicate2(self, nums: List[int]) -> bool:
num_set = set()
for num in nums:
if num in num_set:
return True
num_set.add(num)
return False
def containsDuplicate3(self, nums: List[int]) -> bool:
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return False
def containsDuplicate4(self, nums: List[int]) -> bool:
return len(nums) != len(set(nums))
if __name__ == '__main__':
s = Solution()
nums = [1,2,3,1]
print(s.containsDuplicate(nums))
print(s.containsDuplicate2(nums))
print(s.containsDuplicate3(nums))
print(s.containsDuplicate4(nums))
nums = [1,2,3,4]
print(s.containsDuplicate(nums))
print(s.containsDuplicate2(nums))
print(s.containsDuplicate3(nums))
print(s.containsDuplicate4(nums))
nums = [1,1,1,3,3,4,3,2,4,2]
print(s.containsDuplicate(nums))
print(s.containsDuplicate2(nums))
print(s.containsDuplicate3(nums))
print(s.containsDuplicate4(nums))
输出：
True
True
True
True
False
False
False
False
True
True
True
True
2. 存在重复元素 Contains Duplicate II
给你一个整数数组 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 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^90 <= k <= 10^5
代码： 多种方法实现
from typing import List
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
n = len(nums)
for i in range(n):
for j in range(i + 1, min(i + k + 1, n)):
if nums[i] == nums[j]:
return True
return False
def containsNearbyDuplicate2(self, nums: List[int], k: int) -> bool:
num_index = {}
for i in range(len(nums)):
if nums[i] in num_index and i - num_index[nums[i]] <= k:
return True
num_index[nums[i]] = i
return False
def containsNearbyDuplicate3(self, nums: List[int], k: int) -> bool:
n = len(nums)
if k >= n:
k = n - 1
num_set = set(nums[:k + 1])
if len(num_set) != k + 1:
return True
for i in range(k + 1, n):
num_set.remove(nums[i - k - 1])
if nums[i] in num_set:
return True
num_set.add(nums[i])
return False
if __name__ == '__main__':
s = Solution()
nums = [1,2,3,1]
print(s.containsNearbyDuplicate(nums, 3))
print(s.containsNearbyDuplicate2(nums, 3))
print(s.containsNearbyDuplicate3(nums, 3))
nums = [1,0,1,1]
print(s.containsNearbyDuplicate(nums, 1))
print(s.containsNearbyDuplicate2(nums, 1))
print(s.containsNearbyDuplicate3(nums, 1))
nums = [1,2,3,1,2,3]
print(s.containsNearbyDuplicate(nums, 2))
print(s.containsNearbyDuplicate2(nums, 2))
print(s.containsNearbyDuplicate3(nums, 2))
输出：
True
True
True
True
True
True
False
False
False
3. 存在重复元素 Contains Duplicate III
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0 输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2 输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3 输出：false
提示：
0 <= nums.length <= 2 * 10^4-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^40 <= t <= 2^31 - 1
代码： 多种方法实现
from typing import List
import bisect
class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
n = len(nums)
for i in range(n):
for j in range(i + 1, min(i + k + 1, n)):
if abs(nums[i] - nums[j]) <= t and abs(i - j) <= k:
return True
return False
def containsNearbyAlmostDuplicate2(self, nums: List[int], k: int, t: int) -> bool:
n = len(nums)
if t < 0 or k <= 0:
return False
bst = []
for i in range(n):
idx = bisect.bisect_left(bst, nums[i] - t)
if idx < len(bst) and abs(bst[idx] - nums[i]) <= t:
return True
bisect.insort(bst, nums[i])
if i >= k:
bst.remove(nums[i - k])
return False
def containsNearbyAlmostDuplicate3(self, nums: List[int], k: int, t: int) -> bool:
if t < 0 or k <= 0:
return False
n = len(nums)
dic = dict()
w = t + 1
for i in range(n):
m = nums[i] // w
if m in dic:
return True
elif m - 1 in dic and abs(nums[i] - dic[m - 1]) < w:
return True
elif m + 1 in dic and abs(nums[i] - dic[m + 1]) < w:
return True
dic[m] = nums[i]
if i >= k:
del dic[nums[i - k] // w]
return False
if __name__ == '__main__':
s = Solution()
nums = [1,2,3,1]
print(s.containsNearbyAlmostDuplicate(nums, 3, 0))
print(s.containsNearbyAlmostDuplicate2(nums, 3, 0))
print(s.containsNearbyAlmostDuplicate3(nums, 3, 0))
nums = [1,0,1,1]
print(s.containsNearbyAlmostDuplicate(nums, 1, 2))
print(s.containsNearbyAlmostDuplicate2(nums, 1, 2))
print(s.containsNearbyAlmostDuplicate3(nums, 1, 2))
nums = [1,5,9,1,5,9]
print(s.containsNearbyAlmostDuplicate(nums, 2, 3))
print(s.containsNearbyAlmostDuplicate2(nums, 2, 3))
print(s.containsNearbyAlmostDuplicate3(nums, 2, 3))
输出：
True
True
True
True
True
True
False
False
False
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/