[LeetCode] 220. Contains Duplicate III

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Constraints:

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

存在重复元素III。

这道题的前两个版本没什么可说的，这里我直接给出版本三的题解。这道题问的是数组中是否存在两个数他们之间的绝对值 <= t 同时他们的i ndex <= k。

思路是用treeset。treeset的特点是里面所有元素是unique的而且所有元素是递增的，所以这道题我们维护一个size为K的treeset。同时treeset有两个函数，floor()可以找到treeset中比当前数字小的数字中最大的那一个，ceiling()可以找到treeset中比当前数字大的数字中最小的那一个。这样代码就呼之欲出了。同时记得需要将treeset里面所有的数字都convert成long型，否则如果K足够大，比如等于Integer.MAX_VALUE的时候，代码是跑不过去的。

时间O(nlongk) - treeset的底层是红黑树实现的

空间O(k) - 最多只放了K个元素

Java实现

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

LeetCode 题目总结