MENU

LeetCode220. Contains Duplicate III(滑动窗口)

2019 年 03 月 03 日 • 阅读: 1503 • LeetCode阅读设置

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日 星期日