【LeetCode每日一题】220. 存在重复元素 III

公众号guangcity

发布于 2021-04-22 11:44:38

2640

发布于 2021-04-22 11:44:38

文章被收录于专栏：光城(guangcity)

【LeetCode每日一题】220. 存在重复元素 III

今日题目220题，每日一题微信交流群可以点击右下角：合作转载->联系我，备注：刷题，拉你入群。

题目：

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

题解：

本题可以基于滑动窗口，可以采用桶、map、set、multiset等数据结构解决这道题目。

注意处理的时候加减操作会越界，需要转为long long处理。

滑动窗口+multiset

维护长度为k+1元素的滑动窗口，窗口内元素从左到右插入，并查询之前是否存在满足条件的元素，查找到了就返回true，否则继续移动窗口即可。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<long long> s;
        int i = 0, j = 0, n = nums.size();
        while (j < n) {
            while (j < n && j - i <= k) {
                // [nums[i] - k, nums[i] + k]
                auto iter = s.lower_bound((long long)nums[j] - t);
                if (iter != s.end() && *iter <= (long long)nums[j] + t) return true;
                s.insert(nums[j++]);
            }
            s.erase(nums[i++]);
        }
        return false;
    }
};

滑动窗口+桶

同上述方法维护滑动窗口，区别在于元素处理，这里采用map记录每个桶对应的元素是谁，如果已经有这个桶id了，那么就返回true，因为再次出现的元素两个一定满足<=t，而由于也在窗口内，所以满足条件直接返回true，同时还可以在周边桶会满足条件，分别是+1与-1桶的id，去检查即可。

桶id计算方法是：假设现在数据范围是[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]，t=3，那么我们需要满足[0,1,2,3]均在index=0桶，[4,5,6,7]在index=1桶，依次类推。

那如果数据范围携带负数，例如：[-7,-6,-5,-4,-3,-2,-1,0,1,2]，t=3,我们则需要[-4,-3,-2,-1]为index=-1桶，依次类推，而按照正数的计算num/(t+1)得到的0桶的范围是[-3,-2,-1,0],因此我们要得到-1桶，需要对负数右移一位这样就变成了[-3,-2,01,0]这样数据，此时计算式：(num+1)/(t+1)，此时的桶index=0，我们需要把得到-1,再减去1，便是：(num+1)/(t+1) - 1。

class Solution {
public:
    long long w;
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        // k index
        // t value
        int n = nums.size();
        if (n == 0) return false;

        map<long long, long long> m; // id : value
        w = (long long)t + 1;
        int i = 0, j = 0;
        while (j < n) {
            while (j < n && j - i <= k) {
                int id = getBucketId(nums[j]);
                if (m.count(id)) return true;
                if (m.count(id - 1) && abs(m[id - 1] - nums[j]) <= t) return true;
                if (m.count(id + 1) && abs(m[id + 1] - nums[j]) <= t) return true;
                m[id] = nums[j++];
            }
            // j -i > k
            m.erase(getBucketId(nums[i++]));
        }
        return false;
    }

    int getBucketId(int num) {
        if (num >= 0) return num / w;
        else return (num + 1) / w - 1; // 向右平移一个单位得到的桶index 左移一个单位
    }
};