题解 | 存在重复元素III

题干分析

题目给定我们一个整数数组与两个整数,要求我们找到数组中的一对元素,他们彼此间相隔不超过indexDiff且彼此之间的差值的绝对值不超过valueDiff.如果能找到则返回true,反之返回false

算法思路

由于我们需要在下标相差不超过indexDiff的情况下找到符合要求的值,我们考虑使用滑动窗口管理这indexDiff长度下的数组元素. 由于我们需要找到至少一个符合要求的元素对,因此窗口中的元素有序对我们更有利,因为我们能够使用折半查找的方式优化耗时,因此使用set集合管理窗口中的值.由此没当窗口建立,只要新入窗口的值在窗口中能够找到一个符合条件的值,找到则返回true,反之移动窗口,直至所有数组元素均已如窗口一次.

实现代码

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
        int n = nums.size();
        // 滑动窗口
        set<int> window;
        for (int i = 0; i < n; i++) {
            // 移除最左边的元素
            if (i > indexDiff) window.erase(nums[i - indexDiff - 1]);
            // 取得第一个大于等于nums[i] - valueDiff的元素
            auto it = window.lower_bound(nums[i] - valueDiff);
            // 判断是否存在满足条件的下标对
            if (it != window.end() && *it <= nums[i] + valueDiff) return true;
            // 添加当前元素
            window.insert(nums[i]);
        }
        return false;
    }
};

复杂度分析

• 时间复杂度: 每个数组元素至少一次进入窗口,窗口使用set管理,每次进出元素耗时O(logn),折半查找耗时O(logn),因此总计为O(nlogn).
• 空间复杂度: 使用额外的空间set对窗口元素进行管理与判断,空间复杂度为O(n).