Leetcode 220. 存在重复元素 III (set加滑动窗口优化)

17
四月
2021

直接做时间复杂度是O(N^2)

预期优化到O(nlogn)

在遍历的过程中,维护k个元素的set,当元素个数大于k以后,就删掉nums[i - k]元素,

我们在log(N)的时间找到第一个大于等于nums[i]-t元素,在看看他是否小于等于nums[i]-t,如果找到,就满足要求。

typedef long long LL;
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<LL> treeMap;
        for(int i = 0; i < nums.size(); i++){
            auto it = treeMap.lower_bound((LL)nums[i] - t);
            if(it != treeMap.end() && *it <= ((LL)nums[i] + t)){
                return true;
            }
            treeMap.insert(nums[i]);
            if(treeMap.size() > k){
                treeMap.erase(nums[i - k]);
            }
        }
        return false;
    }
};

 

 

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员