# 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

### 代码

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