220. Contains Duplicate III解题报告

Description:

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.

Link:

https://leetcode.com/problems/contains-duplicate-iii/description/

解题方法：

sliding window，用treeset储存k + 1个数, 每次遇到一个新的数，在set里面找离它最近的两个数。

Time Complexity：

Nlg(k)

完整代码：

//c++
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
         int len = nums.size();
        if(!len || k < 1 || t < 0)
            return false;
        set<long> S;
        for(int start = 0, end = 0; end < len; end++) {
            int curr = nums[end];
            if(S.size() >= k + 1)
                S.erase(nums[start++]);
            if(S.find(curr) != S.end())
                return true;
            S.insert(curr);
            set<long>::iterator it = S.find(curr);
            if(it != S.begin()) {
                it--;
                if(abs(*it++ - curr) <= t)
                    return true;
            }
            it++;
            if(it != S.end())
                if(abs(*it - curr) <= t)
                    return true;
        }
        return false;
    }
//Java
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len = nums.length;
        if(len == 0 || k < 1 || t < 0)
            return false;
        TreeSet<Long> S = new TreeSet<>();
        for(int start = 0, end = 0; end < len; end++) {
            Long curr = (long) nums[end];
            Long temp = (long) nums[start];
            if(S.size() >= k + 1) {
                S.remove(temp);
                ++start;
            }
            if(S.contains(curr))
                return true;
            if(S.ceiling(curr) != null)
                if(Math.abs(S.ceiling(curr) - curr) <= t)
                    return true;
            if(S.floor(curr) != null)
                if(Math.abs(S.floor(curr) - curr) <= t)
                    return true;
            S.add(curr);
        }
        return false;
    }