LeetCode|LeetCode 第 217、219、220 题（存在重复元素） LeetCode第217、219、220题：存在重

LeetCode 第 217 题：存在重复元素
传送门：217. 存在重复元素。

给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:

输入: [1,2,3,1] 输出: true

示例 2:

输入: [1,2,3,4] 输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2] 输出: true

思路1：使用哈希表。
Python 代码：

class Solution: def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """ s = set() for num in nums: if num in s: return True else: s.add(num) return Falseif __name__ == '__main__': nums = [0] s = Solution() result = s.containsDuplicate(nums) print(result)

思路2：排序以后再判断重复。
Python 代码：

class Solution: def containsDuplicate(self, nums): """ :type nums: List[int] :rtype: bool """if len(nums) < 2: return False # 原地排序 nums.sort() for index in range(1, len(nums)): if nums[index] == nums[index - 1]: return True return False

LeetCode 第 219 题：存在重复元素 II
传送门：219. 存在重复元素 II。

【LeetCode|LeetCode 第 217、219、220 题（存在重复元素）】给定一个整数数组和一个整数 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

Python 代码：

class Solution:# 应该写 is not None # 判断存在重复元素的索引之差小于某个数def containsNearbyDuplicate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ # 给定一个整数数组和一个整数 k， # 判断数组中是否存在两个不同的索引 i 和 j， # 使得 nums [i] = nums [j]， # 并且 i 和 j 的差的绝对值最大为 k。# 先判断 nums [i] = nums [j] # 然后判断索引值是否相等，所以索引值可以用 map 存起来。size = len(nums) if size == 0: return Falsemap = dict() for index in range(size): if nums[index] in map and index - map[nums[index]] <= k: # 只要存在就返回了， return True # 更新为最新的索引 map[nums[index]] = index return False

LeetCode 第 220 题：存在重复元素 III
传送门：220. 存在重复元素 III。

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ?。
示例 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

Java 代码：滑动窗口 + 查找表，这里的查找表是能查询上界和下界的 BST。

class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { int len = nums.length; if (len == 0 || k <= 0 || t < 0) { return false; } TreeSet treeSet = new TreeSet<>(); for (int i = 0; i < len; i++) { // 大于等于 nums[i] 的最小数 Integer ceiling = treeSet.ceiling(nums[i]); if (ceiling != null && (long) ceiling - (long) nums[i] <= t) { return true; } // 小于等于 nums[i] 的最大数 Integer floor = treeSet.floor(nums[i]); if (floor != null && (long) nums[i] - (long) floor <= t) { return true; } treeSet.add(nums[i]); if (i >= k) { treeSet.remove(nums[i - k]); } } return false; } }

参考资料：
1、https://blog.csdn.net/qq_20141867/article/details/82024222
使用有序字典。
2、Python 代码，使用自己实现的 BST：https://leetcode.com/problems/contains-duplicate-iii/discuss/174416/Python-balanced-BST-solution
（本节完）