Finley.Hamilton

# 题目

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.

We just call nums[i] and nums[j] friend element in this artical

# 思考

• A sliding window is must

• use a Binary Search Tree to store the element inside the window

• search/insert/remove O(logK) in window

every time we move window by one step, we check the newest element: Does it has some friend element?

It is a search problem, you need to find element in the tree, since BST can provide good search performance. It is ok.

# Code

``````import java.util.*;

/**
* Created by zuo on 15-8-12.
*/
public class ContainsDuplicatedIII {

/**
*
* @param nums
* @param k index diff, means the window can have k+1 element
* @param t value diff
* @return
*/
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if ( k <= 0 || t < 0) {
return false;
}
// the window start (included)
int winStart = 0;
// the window ends (included)
int winEnd = 0;

TreeMap<Integer, Set<Integer>> tree = new TreeMap<Integer, Set<Integer>>();

/**
* cauz winEnd should be included, initialize the window
*/
if (!tree.containsKey(nums[winEnd])) {
tree.put(nums[winEnd], new HashSet<Integer>());
}

while(winEnd < nums.length) {

/**
* reach criterion exception himself
*/
Map.Entry<Integer, Set<Integer>> ceilingEntry = tree.ceilingEntry(nums[winEnd] - t);
Map.Entry<Integer, Set<Integer>> floorEntry = tree.floorEntry(nums[winEnd] + t);
if ((ceilingEntry != null && (ceilingEntry.getKey() != nums[winEnd] || ceilingEntry.getValue().size() > 1) ) || (floorEntry != null && (floorEntry.getValue().size() > 1 || floorEntry.getKey() != nums[winEnd]))) {
return true;
}

/**
* now the window has (winEnd - winStart + 1) elements(window size = element count)
* winStart++ if the window reach biggest
*/
winEnd++;
if (winEnd == nums.length) {
break;
}
if (!tree.containsKey(nums[winEnd])) {
tree.put(nums[winEnd], new HashSet<Integer>());
}
if (winEnd - winStart > k) {
if (tree.containsKey(nums[winStart])) {
tree.get(nums[winStart]).remove(winStart);
if (tree.get(nums[winStart]).size() == 0) {
tree.remove(nums[winStart]);
}
}
winStart++;
}
}
return false;
}

public static void main(String[] args) {
ContainsDuplicatedIII containsDuplicatedIII = new ContainsDuplicatedIII();
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1, 3 ,1 }, 1, 1));//f
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1, 2}, 1, -1));//f
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1}, 1, 1));//f
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,2,3,4,5}, 1,3)); //t
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,3,5,3,1}, 1,3));//t
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,1,1}, 1,0));//t
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,2,3}, 1,0));//f
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{1,1,1}, 0,1));//f
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{ -1 , - 1}, 1, 0));//t`
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{ 1,3,1}, 2, 1));//t
System.out.println(containsDuplicatedIII.containsNearbyAlmostDuplicate(new int[]{ 4,1,6,3}, 100, 1));//t
}
}

``````

### Finley.Hamilton

LeetCode Contains Duplicate

LeetCode Contains Duplicate Mz的博客2016-03-15173 阅读 算法C/C++ Contains Duplicate 原题传送门: https://leetcode.com/problems/contains-duplicate/ Contains Duplicate II 原题传送门......

Mz的博客
2016/03/15
0
0
Percona Server 5.1.65-14.0 发布

Percona 5.1系列的分支5.1.65-14.0发布。2012-09-03.上一个版本是2012-05-25的5.1.63.不想升级到5.5的用户可以使用此版本。 完全改进包括： Percona is glad to announce the release of Per...

fei
2012/09/05
753
0
Leetcode 220. 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 absolute difference between nums[i] and nums[j] is at most t and t......

ShutLove
2017/11/29
0
0
LeetCode：Contains Duplicate II - 判断数组内是否有重复元素2

1、题目名称 Contains Duplicate II（判断数组内是否有重复元素2） 2、题目地址 https://leetcode.com/problems/contains-duplicate-ii/ 3、题目内容 英文：Given an array of integers and ...

2015/10/15
2.7K
0
217. Contains Duplicate - LeetCode

Question 217. Contains Duplicate Solution 题目大意：判断数组中是否有重复元素 思路：构造一个set，不重复就加进去，重复返回true，如果数据量大的话，可以用布隆过滤器 Java实现：...

yysue
2018/07/18
0
0

35分钟前
3
0

forespider
46分钟前
0
0
mysql函数substring_index的用法

substring_index 按索引字符位进行截取字符串 substring_index（“待截取的字符串”，“截取数据依据的字符”，截取字符的位置N） 第三个参数可正，可负。正数表示索引字符前面的字符串，负数...

echojson
46分钟前
2
0

56分钟前
2
0

spring mvc 整体结构 系统监听到请求 -> 通知tomcat -> 根据web.xml 通知相应的拦截器(spring mvc 通常指DispatcherServlet) --> 检查url是否有相匹配的请求实现 --> 拿到请求实现bean的适配...

58分钟前
3
0