LC *220. 存在重复元素 III（滑动窗口）

SakuraTears

发布于 2022-01-13 14:53:42

2410

发布于 2022-01-13 14:53:42

文章被收录于专栏：从零开始的Code生活

题目

思路

采用暴力法检查所有元素会超时，可以采用STL的set自动将窗口中的元素排序。

然后采用滑动窗口思想

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

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

原始发表：2021年04月17日，如有侵权请联系 cloudcommunity@tencent.com 删除

set