Leetcode 220. Contains Duplicate III

triplebee

发布于 2018-01-12 14:45:56

4680

发布于 2018-01-12 14:45:56

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础计算机视觉与深度学习基础

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.

219的再升级版，不但要求下标差的绝对值不超过k，还要求数值差的绝对值不超过t。

最外层遍历数组，对于每一个位置，我们需要知道它前k个位置中和它在数值上最接近的位置，显然要用到搜索树。

不需要手写，因为set就是搜索树的一种实现。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, long long t) {
        set<long long> s;
        for(int i = 0; i < nums.size(); i++)
        {
            if(i > k) s.erase(nums[i - k - 1]);//删除前面第k+1个元素
            set<long long>::iterator pos = s.lower_bound(nums[i] - t);//如果*pos >= nums[i] - t,则*pos - nums[i] >= -t
            if(pos != s.end() && *pos - nums[i] <= t) return true; //存在*pos，且满足上界条件
            s.insert(nums[i]);
        }
        return false;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-03-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除

absolute