查找

发表于 | 分类于

Leetcode

349. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:
Each element in the result must be unique.
The result can be in any order.

解题思路

简单集合操作set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
       
        Set<Integer> record = new HashSet<Integer>();
        Set<Integer> res = new HashSet<Integer>();
        
        for(int i = 0; i < nums1.length; ++i){
            record.add(nums1[i]);
        }
        
        for(int i = 0; i < nums2.length; ++i){
            if(record.contains(nums2[i])){
                res.add(nums2[i]);
            }
        }
        
        int []A = new int[res.size()];
        int i = 0;
        for(int a : res){
            A[i++] = a;
        }
        
        return A;
    }
}

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
1
Two Points
  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
1
HashTable, the memory of  hashtable is smaller than hashmap
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
1
2
If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.

解题思路

简单map操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> record = new HashMap<Integer, Integer>();
        List<Integer> res = new ArrayList<Integer>();
        
        for(int i = 0; i < nums1.length; ++i){
            if(record.containsKey(nums1[i])){
                record.put(nums1[i], record.get(nums1[i]) + 1);
            }
            else{
                record.put(nums1[i], 1);
            }
        }
        
        for(int i = 0; i < nums2.length; ++i){
            //注意判断record中值为0的键
            if(record.containsKey(nums2[i]) && record.get(nums2[i]) > 0){
                res.add(nums2[i]);
                record.put(nums2[i], record.get(nums2[i])-1);
            }
        }
        
        int []A = new int[res.size()];
        int i = 0;
        for(int a : res){
            A[i++] = a;
        }
        
        return A;
    }
}

242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

解题思路

简单的map操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        
        Map<Character, Integer> record = new HashMap<Character, Integer>();
        
        for(int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            if(record.containsKey(c)){
                record.put(c, record.get(c) + 1);
            }
            else{
                record.put(c, 1);
            }
        }
        
        for(int i = 0;  i < t.length(); ++i){
            char c = t.charAt(i);
            if(record.containsKey(c) && record.get(c) > 0){
                record.put(c, record.get(c) - 1);
            }
            else{
                return false;
            }
        }
        
        return true;
    }
}

聪明人的简洁做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isAnagram(String s, String t) {
        int []alphabet = new int[256];
        
        for(int i = 0; i < s.length(); ++i){
            ++alphabet[s.charAt(i)];
        }
        
        for(char c : t.toCharArray()){
            --alphabet[c];
        }
        
        for(int i : alphabet){
            if(i != 0){
                return false;
            }
        }
        
        return true;
    }
}

202. Happy Number

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

1
2
3
4
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

解题思路

Set保存着82, 68, 100等等…一旦出现了重复值，那么这个数就不可能是happy number了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> set = new HashSet<Integer>();        
        int result = 0;
        
        while(n != 1){
            result = 0;
            while(n != 0){
                result += Math.pow(n % 10, 2);
                n /= 10;
            }
            if(set.contains(result)){
                return false;
            }
            set.add(result);
            n = result;
        }
        
        return true;
    }
}

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

1
2
3
4
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

解题思路

很简单的键值映射关系，这边有个坑是关于HashMap的get和put操作，最好看下源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean wordPattern(String pattern, String str) {
        Map<Character, String> map = new HashMap<Character, String>();
        String []strings = str.split(" ");
        
        if(strings.length != pattern.length()){
            return false;
        }
            
        for(int i = 0; i < pattern.length(); ++i){
            char c = pattern.charAt(i);
            if(map.containsKey(c)){
                if(!map.get(c).equals(strings[i])){
                    return false;
                }
            }
            else if(map.containsValue(strings[i])){
                return false;
            }
            map.put(c, strings[i]);
        }
        
        return true;
    }
}

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,

1
2
3
4
5
Given "egg", "add", return true.
Given "foo", "bar", return false.
Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

解题思路

将字符映射其最近所存储的位置，一旦发现两者的存储位置不同，返回false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isIsomorphic(String s, String t) {
        int []m1 = new int[256];
        int []m2 = new int[256];
        int n = s.length();
        
        for(int i = 0; i < n; ++i){
            char c1 = s.charAt(i);
            char c2 = t.charAt(i);
            
            if(m1[c1] != m2[c2]){
                return false;
            }
            
            m1[c1] = i + 1;
            m2[c2] = i + 1;
        }
        
        return true;
    }
}

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Input:
"tree"
Output:
"eert"
Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
-------------------------------------------------------------------------------------
Input:
"cccaaa"
Output:
"cccaaa"
Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.
-------------------------------------------------------------------------------------
Input:
"Aabb"
Output:
"bbAa"
Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

解题思路

借助HashMap和TreeMap实现
HashMap用来统计每次字符出现的频率
TreeMap维护频率和字符列表，因为字符出现的频率可能重复，所以使用list来维护

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public String frequencySort(String s) {
        HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
        TreeMap<Integer, List<Character>> sort = new TreeMap<Integer, List<Character>>(
                new Comparator<Integer>(){
                    @Override
                    public int compare(Integer o1, Integer o2){
                        return o1 == o2 ? 0 : (o1 < o2 ? 1 : -1);
                    }
                }
        );
        for(char c : s.toCharArray()){
            if(freq.containsKey(c)){
                freq.replace(c, freq.get(c) + 1);
            }
            else{
                freq.put(c, 1);
            }
        }
        for(Map.Entry<Character, Integer> entry : freq.entrySet()){
            char c = entry.getKey();
            int cnt = entry.getValue();
            if(sort.containsKey(cnt)){
                sort.get(cnt).add(c);
            }
            else{
                List<Character> list = new ArrayList<Character>();
                list.add(c);
                sort.put(cnt, list);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(Map.Entry<Integer, List<Character>> entry : sort.entrySet()){
            int cnt = entry.getKey();
            for(char c : entry.getValue()){
                int i = 0;
                while(i++ < cnt){
                    sb.append(c);
                }
            }
        }
        
        return sb.toString();
    }
}

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

解题思路

由于输入的数组并不是排序数组，所以直接使用对撞指针是不行的
使用Map找complement值

通常做法：首先将所有元素存入，接着遍历索引直到找到匹配的值；
有个小技巧：
只需要遍历一次，每次存入元素之前，就可以判断是否存在匹配的值，并且可以省去判断自否为重复索引的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> index = new HashMap<Integer, Integer>();
        
        for(int i = 0; i < nums.length; ++i){
            int complement = target - nums[i];
            if(index.containsKey(complement)){
                int []A = new int[]{index.get(complement), i};
                return A;
            }
            index.put(nums[i], i);
        }
        
        return null;
    }
}

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

先对数组进行排序，然后基于对撞指针的想法，将三个元素相加，寻找和为0的组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; ++i){
            //去重操作
            if(i != 0 && nums[i] == nums[i-1]){
                continue;
            }
            
            int p = i + 1;
            int q = nums.length - 1;
            while(p < q){
                int sum = nums[i] + nums[p] + nums[q];
                if(sum == 0){
                    list2.add(Arrays.asList(nums[i], nums[p], nums[q]));
                    //while去重操作
                    //边界条件是指针先往前走一步，接着回头看是否重复
                    while(++p < q && nums[p-1] == nums[p]){}
                    while(p < --q && nums[q+1] == nums[q]){}
                }
                else if(sum < 0){
                    ++p;
                }
                else{
                    --q;
                }
            }
        }
        
        return list2;
    }
}

18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

1
2
3
4
5
6
7
8
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题思路：

与上一题一样的思路，只不过多了一层循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list2 = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 3; ++i){
            if(i != 0 && nums[i-1] == nums[i]){
                continue;
            }
            
            for(int j = i+1; j < nums.length - 2; ++j){
                if(j != i + 1 && nums[j-1] == nums[j]){
                    continue;
                }
                
                int p = j+1;
                int q = nums.length-1;
                while(p < q){
                    int sum = nums[i] + nums[j] + nums[p] + nums[q];
                    if(sum == target){
                        Integer []A = {nums[i], nums[j], nums[p], nums[q]};
                        list2.add(Arrays.asList(A));
                        
                        while(++p < q && nums[p-1] == nums[p]){}
                        while(p < --q && nums[q+1] == nums[q]){}
                    }
                    else if(sum < target){
                        ++p;
                    }
                    else{
                        --q;
                    }
                }
            }
        }
        
        return list2;
    }
}

16. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
3
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

解题思路：

类似于题目 3Sum；判别条件变了而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closestValue = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; ++i){
            if(i != 0 && nums[i-1] == nums[i]){
                continue;
            }
            
            int p = i + 1;
            int q = nums.length - 1;
            while(p < q){
                int sum = nums[i] + nums[p] + nums[q];
                int remain = sum - target;
                if(remain == 0){
                    return target;
                }
                else if(remain < 0){
                    ++p;        
                }
                else{
                    --q;
                }
                closestValue = (Math.abs(sum - target) < Math.abs(closestValue - target)) ?
                                    sum : closestValue;
            }
        }
        
        return closestValue;
    }
}

454. 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2的28次方 to 2的28次方 - 1 and the result is guaranteed to be at most 2的31次方 - 1.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

解题思路

空间换时间，题目也说了数组的长度为 0 <= N <= 500
暴力解法的复杂度为N的四次方，通过HashMap可以降为N的2次方
空间复杂度也是为N的2次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        int result = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for(int a : A){
            for(int b : B){
                map.put(a+b, map.getOrDefault(a+b, 0) + 1);
            }
        }
        
        for(int c : C){
            for(int d : D){
                int remain = 0 - c - d;
                result += map.getOrDefault(remain, 0);
            }
        }
        
        
        return result;
    }
}

49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

解题思路：

将包含的相同字符集和个数的字符串进行分类
相同的Anagram字符串作为HashMap的Key，处理之前先进行排序，使其具有唯一性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        
        for(String str : strs){
            char []chars = str.toCharArray();
            Arrays.sort(chars);
            String s = Arrays.toString(chars);
            
            if(!map.containsKey(s)){
                map.put(s, new ArrayList<String>());
            }
            map.get(s).add(str);
        }
                    
        return new ArrayList<List<String>>(map.values());
    }
}

447. Number of Boomerangs

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

1
2
3
4
5
6
7
8
Input:
[[0,0],[1,0],[2,0]]
Output:
2
Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

解题思路：

PointX与界面上的点距离，利用HashMap维护距离及其相同距离的个数
最后统计有多个对距离相同的边 的个数result

假设distance 为 a，并且个数为1，那么result += 0；
假设distance 为 b，并且个数为2，那么result += 2；
假设distance 为 c，并且个数为3， 那么result += 6。
以此类推（选择问题, 对于每个点m, 都有m-1种选择）

注意distance返回的值越界，不过该题不会越界, 10000 * 10000 小于 2的31次方-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int numberOfBoomerangs(int[][] points) {
        
        int result = 0;
        
        for(int i = 0; i < points.length; ++i){
            HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
            
            for(int j = 0; j < points.length; ++j){
                if(j != i){
                    int dis = distance(points[i][0], points[i][1], points[j][0], points[j][1]);
                    
                    record.put(dis, record.getOrDefault(dis, 0) + 1);
                }
            }
            
            for(int val : record.values()){
                result += val * (val-1);
            }
        }
        
        return result;
    }
    
    private int distance(int x1, int y1, int x2, int y2){
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }
}

149. Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

解题思路：

详见注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class Solution {
    public int maxPoints(Point[] points) {
        int res = 0;
        
        if(points.length < 3){
            return points.length;
        }
        
        for(int i = 0; i < points.length - 1; ++i){
            //Point[i]的与其他points的斜率的计数统计
            HashMap<String, Integer> record = new HashMap<String, Integer>();
            int maxLine = 0;
            int overlap = 0;
            
            //其他点下标从i+1开始，避免重复工作
            for(int j = i + 1; j < points.length; ++j){
                int dx = points[i].x - points[j].x;
                int dy = points[i].y - points[j].y;
                if(dx == 0 && dy == 0){
                    overlap++;
                    continue;	//统计重叠的点
                }
                
                int gcd = getGcd(dx, dy);
                String slope = String.valueOf(dx/gcd) + String.valueOf(dy/gcd);
                
                int cnt = record.getOrDefault(slope, 0);
                record.put(slope, ++cnt);
                maxLine = Math.max(cnt, maxLine);
            }
            
            res = Math.max(res, overlap+maxLine+1);
        }
        
        return res;
    }
    
    //辗转相除法求最大公约数
    private int getGcd(int a, int b){
        if(b == 0){
            return a;
        }
        return getGcd(b, a % b);
    }
}

219. 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 absolute difference between i and j is at most k.

解题思路：

滑动窗口+查找表
滑动窗口的最大为k， 在窗口k内若找到重复的元素，返回true
每次将元素加入Set中，一旦set大小超过k，也就是窗口大小大于k，
那么就可以删除窗口最左端元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> record = new HashSet<Integer>();
        
        for(int i = 0; i < nums.length; ++i){
            if(record.contains(nums[i])){
                return true;
            }
            
            record.add(nums[i]);
            
            if(record.size() == k + 1){
                record.remove(nums[i-k]);
            }
        }
        
        return false;
    }
}

217. Contains Duplicate

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.

解题思路：

简单的Set操作

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> record = new HashSet<Integer>();
        for(int i = 0; i < nums.length; ++i){
            if(record.contains(nums[i])){
                return true;
            }
            record.add(nums[i]);
        }
        
        return false;
    }
}

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 the absolute difference between i and j is at most k.

解题思路：

可以把k看做滑动窗口，对于一个新的数，可以想象成放到这个窗口的最左边或者最右边，如果这个数+t或-t之后落在窗口里，直接返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        
        TreeSet<Long> record = new TreeSet<Long>();
        
        for(int i = 0; i < nums.length; ++i){
            Long floor = record.floor((long)nums[i] + (long)t);
            Long ceiling = record.ceiling((long)nums[i] - (long)t);
            
            if((floor != null && floor >= (long)nums[i]) ||
                (ceiling != null && ceiling <= (long)nums[i])){
                
                return true;
            }
            
            record.add((long)nums[i]);
            
            if(record.size() == k + 1){
                record.remove((long)nums[i-k]);
            }
        }
        
        return false;
    }
}