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 False
if __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。
给定一个整数数组和一个整数 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 False
map = 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<Integer> 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
（本节完）
