220. Contains Duplicate III

Question

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.

Note:

  • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.


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

Thinking:

  • Method 1：brutal force
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len = nums.length;
        for(int i = 0; i <len; i++){
            for(int j = i + 1; j < len && j - i <= k; j++){
                long a = (long)nums[i];
                long b = (long)nums[j];
                if(Math.abs(a - b) <= t)
                    return true;
            }
        }
        return false;
    }
}
  • Method 2: TreeSet
    • 通过TreeSet的subSet方法获取范围内的子集。
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums == null || t < 0 || k < 1) return false;
        TreeSet<Long> set = new TreeSet<>();
        for(int i = 0; i < nums.length; i++){
            SortedSet<Long> sub = set.subSet((long)nums[i] - t, true, (long)nums[i] + t, true);
            if(!sub.isEmpty())
                return true;   
            if(i >= k)
                set.remove((long)nums[i - k]);
            set.add((long)nums[i]);
        }
        return false;
    }
}

二刷

  1. 使用for循环， O（N^2）. 
    class Solution {
 public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
     for(int i = 0; i < nums.length; i++){
         for(int j = i + 1; j < nums.length && j - i <= k; j++){
             if(Math.abs((long)nums[j] - (long)nums[i]) <= t) return true;
         }
     }
     return false;
 }
}
  2. 使用TreeSet来维护K个元素在集合中，我们通过遍历整个数组来判断nums[i] - t, nums[i] + t的子集是不是为空，如果不为空则返回true，不然我们将当前的元素加入集合并移除最开始加入的元素(保证集合中元素的个数)。 
    class Solution {
 public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
     if(k <= 0 || t < 0) return false;
     int len = nums.length;
     TreeSet<Long> set = new TreeSet<>();
     for(int i = 0; i < len; i++){
         Set<Long> subSet = set.subSet((long)nums[i] - t, true, (long)nums[i] + t, true);
         if(!subSet.isEmpty()) return true;
         if(i - k >= 0) set.remove((long)nums[i - k]);
         set.add((long)nums[i]);
     }
     return false;
 }
}