LeetCode220. Contains Duplicate III（滑动窗口）

LeetCode220. Contains Duplicate III（滑动窗口）

• Medium
• Accepted：85,909
• Submissions：442,435

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.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

---

链接

https://leetcode.com/problems/contains-duplicate-iii

题意

给定一个数组，问数组中是否存在两个数满足：这两个数的差不超过t且两个数的下标的差不超过k（差均为绝对值）。

题解

之前这道题LeetCode219. Contains Duplicate II（滑动指针）的升级版，加了一个限制条件及两数的差的绝对值不超过t。

我们依然可以使用滑动指针来解决这道题，只是考虑如果处理两数的差。

实际上对于$abs(v - x) <= t$，我们可以转化为$x - t <= v <= x + t$ ，即判断滑动窗口中是否存在存在一个元素大于等于nums[i]-t且该元素小于等于nums[i]+t，为了使序列有序，我们使用set，然后使用lower_bound来进行查找。时间复杂度$O(nlogn)$。

此外还有一个小的问题是，使用long long避免溢出。

代码

• Runtime: 24 ms, faster than 86.59% of C++ online submissions for Contains Duplicate III.
• Memory Usage: 10.9 MB, less than 35.37% of C++ online submissions for Contains Duplicate III.

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        set <long long> uset;
        for (int i = 0; i < n; ++i)
        {
            if (uset.lower_bound((long long)nums[i] - t) != uset.end()
                && *uset.lower_bound((long long)nums[i] -t) <= (long long)nums[i] + t)
                return true;
            uset.insert((long long)nums[i]);
            if (uset.size() == k + 1) // 保持滑动窗口中始终保持k个元素
                uset.erase((long long)nums[i - k]);
        }
        return false;
    }
};

---

The end.
2019年3月3日 星期日