# [题目描述](https://leetcode-cn.com/problems/contains-duplicate-iii/)  ## 方法1 滑动窗口+二分 - `abs(i-j)<=k`提示我们维护一个大小为k的窗口，在这个窗口内寻找满足`abs(nums[i]-nums[j])<=t`的`i,j` 所以我们希望使用一个「有序集合」去维护长度为 k 的滑动窗口内的数，该数据结构最好支持高效「查询」与「插入/删除」操作： - 查询：能够在「有序集合」中应用「二分查找」，快速找到「小于等于 uu 的最大值」和「大于等于 u 的最小值」（即「有序集合」中的最接近 u 的数(使得abs(nums[i]-nums[j])尽可能地小 只要满足≤t存在 就返回true）。 - 插入/删除：在往「有序集合」添加或删除元素时，能够在低于线性的复杂度内完成（维持有序特性）。 ```java class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { int n = nums.length; // 默认构造方法，可以传Comparator作为参数自定义排序 TreeSet<Long> ts = new TreeSet<>(); for (int i = 0; i < n; i++) { Long u = nums[i] * 1L; // 从 ts 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数） Long l = ts.floor(u); // 从 ts 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数） Long r = ts.ceiling(u); if(l != null && u - l <= t) return true; if(r != null && r - u <= t) return true; // 将当前数加到 ts 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k） ts.add(u); if (i >= k) ts.remove(nums[i - k] * 1L); } return false; } } ``` ## 自定义排序用法 这里只列举自己常用的2种 ### 匿名函数 ```java TreeSet<String> ts = new TreeSet<>((p,q)->(p.length()-q.length())); ``` ### 重写Comparator的compare方法 ```java TreeSet<String> ts = new TreeSet<>(new Comparator<String>(){ @Override public int compare(String a,String b){ return a.length() - b.length(); } }); ``` ## 例子：给二维数组按某列排序 ```java int[][] twoDims = new int[][]; Arrays.sort(twoDims,new Comparator<int[]>(){ @Override public int compare(int[] o1, int[] o2) { if(o1[0]==o2[0]){ return o1[1] - o2[1]; } return o1[0] - o2[0]; } }); ```