[LeetCode]Contains Duplicate III
题目描述：
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
题目大意：
给定一个整数数组，判断其中是否存在两个不同的下标i和j满足：| nums[i] - nums[j] | &= t 并且 | i - j | &= k
解题思路：
解法I：&滑动窗口& + 字典（桶）
如果： | nums[i] - nums[j] | &= t
等价： | nums[i] / t - nums[j] / t | &= 1
推出： | floor(nums[i] / t) - floor(nums[j] / t) | &= 1
等价： floor(nums[j] / t) & {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 式d
其中式b是式c的充分非必要条件，因为逆否命题与原命题等价，所以：
如果： floor(nums[j] / t) & {floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1} 非d
推出： | nums[i] - nums[j] | & t
因此只需要维护一个大小为k的窗口（字典）numDict，其中键为nums[i] / t，值为nums[i]。
遍历数组nums时，检查nums[i]与键集{floor(nums[i] / t) - 1, floor(nums[i] / t), floor(nums[i] / t) + 1}对应的值的差值即可。
Python代码：
class Solution:
# @param {integer[]} nums
# @param {integer} k
# @param {integer} t
# @return {boolean}
def containsNearbyAlmostDuplicate(self, nums, k, t):
if k & 1 or t & 0:
return False
numDict = collections.OrderedDict()
for x in range(len(nums)):
key = nums[x] / max(1, t)
for m in (key, key - 1, key + 1):
if m in numDict and abs(nums[x] - numDict[m]) &= t:
return True
numDict[key] = nums[x]
numDict.popitem(last=False)
return False
解法II：&滑动窗口& + TreeSet
参考LeetCode Discuss：/discuss/38177/java-o-n-lg-k-solution
TreeSet数据结构（Java）使用红黑树实现，是平衡二叉树的一种。
该数据结构支持如下操作：
1. floor()方法返set中&给定元素的最大元素；如果不存在这样的元素，则返回 null。
2. ceiling()方法返回set中&给定元素的最小元素；如果不存在这样的元素，则返回 null。
Java代码：
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if(k & 1 || t & 0)
TreeSet&Integer& set = new TreeSet&Integer&();
for(int i = 0; i & nums. i++){
int n = nums[i];
if(set.floor(n) != null && n &= t + set.floor(n) ||
set.ceiling(n) != null && set.ceiling(n) &= t + n)
set.add(n);
if (i &= k)
set.remove(nums[i - k]);
本文链接：请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
如果您喜欢这篇博文，欢迎您捐赠书影博客：
没有类似日志
欢迎来到的博客
本博客基于
提供云计算资源
周一周二周三周四周五周六周日
15161718192021Snail—1-9这9个数目字划分成三个3位数，第一个分别是第二、三个的2倍，3倍 - 人工智能当前位置:& &&&Snail—1-9这9个数目字划分成三个3位数，第一个分别Snail—1-9这9个数目字划分成三个3位数，第一个分别是第二、三个的2倍，3倍&&网友分享于：&&浏览：0次Snail—1-9这9个数字划分成三个3位数，第一个分别是第二、三个的2倍，3倍//1-9这9个数字划分成三个3位数，第一个分别是第二、三个的2倍，3倍
void myGetThreeNum(){
int &span style=&font-family: Arial, Helvetica, sans-&&arr&/span&&span style=&font-family: Arial, Helvetica, sans-&&[10],&/span&
for (int i = 123; i * 3 & 987; i++) {
//将arr 的 前sizeof(int) * 10个字节 清为0
memset(arr,0,sizeof(int) * 10);
arr[i / 100] = 1;
arr[i / 10 % 10] = 1;
arr[i % 10] = 1;
j = i * 2;
arr[j / 100] = 1;
arr[j / 10 % 10] = 1;
arr[j % 10] = 1;
k = i * 3;
arr[k / 100] = 1;
arr[k / 10 % 10] = 1;
arr[k % 10] = 1;
for (int x = 1; x & 10; x++) {
sum += arr[x];
if (sum == 9) {
printf(&a = %d,b = %d,c = %d\n&,k,j,i);
版权声明：本文为博主原创文章，未经博主允许不得转载。
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 1234567891011 Copyright & &&版权所有Contains Duplicate I
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
用一个集合记录之前遇到过的数字，如果新的数字已经在集合中出现过了，则说明有重复。
public class Solution {
public boolean containsDuplicate(int[] nums) {
Set&Integer& set = new HashSet&Integer&();
for(int i = 0; i & nums. i++){
if(set.contains(nums[i]))
set.add(nums[i]);
Contains Duplicate II
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
时间 O(N) 空间 O(K)
同样使用集合，但这次我们要维护集合的大小不超过k，相当于是记录一个宽度为k的窗口中出现过的数字。
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set&Integer& set = new HashSet&Integer&();
for(int i = 0; i & nums. i++){
if(set.contains(nums[i]))
set.add(nums[i]);
if(set.size()&k) set.remove(nums[i-k]);
Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
二叉搜索树
时间 O(NlogK) 空间 O(K)
要求判断之前是否存在差值小于t的数字，我们需要知道在当前数字x两边的数字，即最大的小于x的数字和最小的大于x的数字。二叉搜索树有也有这样的性质，它的左节点是最大的小于根节点的数字，它的右节点是最小的大于根节点的数字。这里我们用TreeSet这个类，它实现了BST，并有集合的性质，非常适合这题。我们同样也是维护一个大小为k的TreeSet。
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet&Integer& set = new TreeSet&Integer&();
for(int i = 0; i & nums. i++){
int x = nums[i];
// 最大的小于x的数字
if(set.ceiling(x) != null && set.ceiling(x) &= t + x)
// 最小的大于x的数字
if(set.floor(x) != null && x &= t + set.floor(x))
set.add(x);
if(set.size()&k) set.remove(nums[i-k]);Given an array of integers and an integer k, return true if and only if there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k. (Old Version)
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k. (New Version)
这道题是之前那道的延伸，不同之处在于那道题只要我们判断下数组中是否有重复值，而这道题限制了数组中只许有一组重复的数字，而且他们坐标差不能超过k。那么我们首先需要一个哈希表，来记录每个数字和其坐标的映射，然后我们需要一个变量d来记录第一次出现重复数字的坐标差。由于题目要求只能有一组重复的数字，所以我们在遇到重复数字时，首先判断d是否已经存了值，如果d已经有值了，说明之前有过了重复数字，则直接返回false即可。如果没有，则此时给d附上值。在网上看到有些解法在这里就直接判断d和k的关系然后返回结果了，其实这样是不对的。因为题目要求只能有一组重复数，就是说如果后面又出现了重复数，就没法继续判断了。所以正确的做法应该是扫描完整个数组后在判断，先看d有没有存入结果，如果没有，则说明没出现过重复数， 返回false即可。如果d有值，再跟k比较，返回对应的结果。OJ的test case没有包含所有的情况，比如当nums = [1, 2, 3, 1, 3], k = 3时，实际上应该返回false，但是有些返回true的算法也能通过OJ。个人认为正确的解法应该入下：
// Wrong Soulution
class Solution {
bool containsNearbyDuplicate(vector&int&& nums, int k) {
unordered_map&int, int&
int d = 0;
for (int i = 0; i & nums.size(); ++i) {
if (m.find(nums[i]) != m.end()) {
if (d & 0) return false;
d = i - m[nums[i]];
m[nums[i]] =
return d == 0 ? false : d &=
坑爹啊，题目要求变了，那么就没啥歧义了，正确解法如下：
class Solution {
bool containsNearbyDuplicate(vector&int&& nums, int k) {
unordered_map&int, int&
for (int i = 0; i & nums.size(); ++i) {
if (m.find(nums[i]) != m.end() && i - m[nums[i]] &= k) return true;
else m[nums[i]] =
return false;
相似题目：
阅读(...) 评论()