【4.17】LeetCode每日一题· 存在重复元素 III

2021年04月17日 16时55分

标签： LeetCode 滑动窗口树形结构

## 题目描述
给你一个整数数组`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
```

#### 示例2
```
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true
```

#### 示例3
```
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
```

#### 提示
```
0 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^4
0 <= t <= 2^31 - 1
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/contains-duplicate-iii "题目链接")

## 解题思路
可以使用长度为`k+1`的滑动窗口，并维护滑动窗口内的数字是**有序**的。这样每滑动一次窗口，现将滑出窗口的元素从滑动窗口中删去，然后插入当前新加入的元素，并找到其前一个位置的元素值和后一个位置的元素值。由于滑动窗口是有序的，因此可以判断当前加入元素和前一个位置的元素值之差的绝对值和后一个位置的元素值之差的绝对值中的较小值是否小于`t`，即判断
```math
\displaystyle
\min\left(\left|nums[i]-nums[i-1]\right|, \left|nums[i+1]-nums[i]\right|\right) \leq t
```
是否成立，其中`i`为当前元素所插入的位置。如果该式成立，则说明存在两个不同下标使得`abs(nums[i]-nums[j]) <= t`；否则继续滑动窗口，直到数组结束为止。

我们可以使用`set`这一数据结构维护滑动窗口内的数字有序。并通过`lower_bound`函数找到大于等于当前插入元素的第一个元素（将该位置减去1即为小于当前插入元素的最后一个元素的位置）。需要注意的是，`set`只重载了`++, --, *`等运算符，而并未重载二元运算符，所以找前一个位置的时候较为啰嗦。

除此以外，原来我以为需要使用`multiset`实现，其实是不用的。因为如果`set`中存在两个相同元素，那么其差值为0一定小于`t`，此时已经判断为`true`跳出函数了；因此集合中不可能存在相同的元素，直接使用`set`即可。

另外需要注意，两个`int`相**加减**（两个大数相加、一个大正数减去一个大负数、一个大负数减去一个大正数）可能导致越界，因此在判断差值是否小于`t`的时候，需要将类型转化为`long long`。

还有时间复杂度为$$O(n)$$的解法，见[https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/](https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/)。

## 代码
```cpp
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        k = min(k, (int)nums.size()-1);
        if(k <= 0) return 0;

int i, j, pre;
        set<int> sorted;
        pre = nums[0];
        sorted.insert(nums[0]);
        set<int>::iterator greater, fewer;
        for(i = 1; i <= k; i++){
            greater = sorted.lower_bound(nums[i]);
            fewer = --sorted.lower_bound(nums[i]);
            if(greater != sorted.end()){
                if(abs((long long)nums[i]-*greater) <= (long long)t){
                    return true;
                }
            }
            if(greater != sorted.begin()){
                if(abs((long long)nums[i]-*fewer) <= (long long)t){
                    return true;
                }
            }
            sorted.insert(nums[i]);
        }
        for(i = 1, j = k+1; j < nums.size(); i++, j++){
            sorted.erase(pre);
            greater = sorted.lower_bound(nums[j]);
            fewer = --sorted.lower_bound(nums[j]);
            if(greater != sorted.end()){
                if(abs((long long)nums[j]-*greater) <= (long long)t){
                    return true;
                }
            }
            if(greater != sorted.begin()){
                if(abs((long long)nums[j]-*fewer) <= (long long)t){
                    return true;
                }
            }
            sorted.insert(nums[j]);
            pre = nums[i];
        }
        return false;
    }
};
```

## 用时和内存
> 执行用时：48 ms，在所有 C++提交中击败了32%的用户
> 内存消耗：18.3 MB，在所有 C++提交中击败了5.15%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.17】LeetCode每日一题· 存在重复元素 III

所有评论

暂无评论

新增评论