题目： 给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 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
解题思路：
先排序，然后比较相邻两个数即可，若存在相等的数，返回True,不存在返回False,时间复杂度为O(nlog(n))使用哈希表方法1：代码实现：
C++: class Solution { public: bool containsDuplicate(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i=1;i<nums.size();i++) { if(nums[i]==nums[i-1]) return true; } return false; } };方法二：哈希表实现：
Python: class Solution: def containsDuplicate(self, nums: List[int]) -> bool: #如果数组的长度大于哈希表（里面含有的不同元素个数）的长度，则返回True,否则，返回false return len(nums) > len(set(nums))题目：给定一个整数数组和一个整数 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
解题思路：哈希表的方法
维护一个哈希表，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字时间复杂度：O(n)，n为数组长度 Python class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: #字典保存键值对 dct = {} for i in range(len(nums)): if nums[i] in dct and dct[nums[i]] + k >= i: return True dct[nums[i]] = i return False题目： 在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 ķ 。
如果存在则返回 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
最优解法：利用桶的原理O(n)，Python3
定义桶的大小是t+1, nums[i]//(t+1)决定放入几号桶,这样在一个桶里面的任意两个的绝对值差值都<=t 例如t=3, nums=[0 ,5, 1, 9, 3,4],那么0号桶就有[0,1,3],1号桶就有[4,5],2号桶就有[9]
先不考虑索引差值最大为K的限制，那么遍历nums每一个元素，并把他们放入相应的桶中，有两种情况会返回True
要放入的桶中已经有其他元素了，这时将nums[i]放进去满足差值<=t可能存在前面一个桶的元素并且与nums[i]的差值<=t 或者 存在后面一个桶的元素并且与nums[i]的差值<=t根据返回True的第一个条件，可以知道前后桶的元素最多也只能有一个。接着考虑限制桶中的索引差最大为K,当i>=k的时候：
我们就要去删除存放着nums[i-k]的那个桶(编号为nums[i-k]//(t+1))这样就能保证遍历到第i+1个元素时，全部桶中元素的索引最小值是i-k+1，就满足题目对索引的限制了 Python实现： class Solution: def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool: if t < 0 or k < 0: return False buckets = {} bucket_size = t + 1 # 桶的大小设成t+1更加方便 for i in range(len(nums)): bucket_num = nums[i] // bucket_size # 放入哪个桶，对桶进行编号 if bucket_num in buckets: # 桶中已经有元素了，即该桶中存在满足题目条件的两个索引 return True buckets[bucket_num] = nums[i] # 把nums[i]放入桶中 if (bucket_num - 1) in buckets and abs(buckets[bucket_num - 1] - nums[i]) <= t: # 检查前一个桶 return True if (bucket_num + 1) in buckets and abs(buckets[bucket_num + 1] - nums[i]) <= t: # 检查后一个桶 return True # 如果不构成返回条件，那么当i >= k 的时候就要删除旧桶了，以维持桶中的元素索引跟下一个i+1索引只差不超过k if i >= k: buckets.pop(nums[i-k]//bucket_size) return False题目： 在大小为 2N 的数组 A 中有 N+1 个不同的元素，其中有一个元素重复了 N 次。返回重复了 N 次的那个元素。
示例 1： 输入：[1,2,3,3] 输出：3
示例 2： 输入：[2,1,2,5,3,2] 输出：2
示例 3： 输入：[5,1,5,2,5,3,5,4] 输出：5
提示： 4 <= A.length <= 10000 0 <= A[i] < 10000 A.length 为偶数
解题思路：
由于A中含有N+1个不同的元素，而仅存在一个重复N次的元素，那么这个元素必定与其左右相邻元素都相等，否则该元素便位于最后一位 C++实现： class Solution { public: int repeatedNTimes(vector<int>& A) { int len = A.size(); for (int i = 0; i < len - 2; i++) { if (A[i] == A[i+1] || A[i] == A[i+2]) { return A[i]; } } // 上面循环没找到，那必然是最后一个数，如[1,2,3,1] return A[len - 1]; } };解题思路2：直接利用哈希表
Python实现： class Solution: def repeatedNTimes(self, A: List[int]) -> int: data = dict() for i in A: data[i] = data.get(i,0) + 1 for (key,value) in data.items(): if value == len(A) //2: return key