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^9
0 <= 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 - 1
0 <= k <= 10^4
0 <= 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
