当前位置:网站首页>力扣(LeetCode)220. 存在重复元素 III(2022.08.08)
力扣(LeetCode)220. 存在重复元素 III(2022.08.08)
2022-08-09 10:28:00 【ChaoYue_miku】
给你一个整数数组 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 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/contains-duplicate-iii
方法一:滑动窗口 + 有序集合
C++提交内容:
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
int n = nums.size();
set<int> rec;
for (int i = 0; i < n; i++) {
auto iter = rec.lower_bound(max(nums[i], INT_MIN + t) - t);
if (iter != rec.end() && *iter <= min(nums[i], INT_MAX - t) + t) {
return true;
}
rec.insert(nums[i]);
if (i >= k) {
rec.erase(nums[i - k]);
}
}
return false;
}
};
边栏推荐
猜你喜欢
随机推荐
Umi Hooks
上传张最近做的E2用的xmms的界面的截图
[贴装专题] 基于多目视觉的手眼标定
LM小型可编程控制器软件(基于CoDeSys)笔记二十六:plc的数据存储区(模拟量输入通道部分)
By asking where the variables are stored, the shepherd boy laughed and said to use pointers, Go lang1.18 introductory refining tutorial, from Bai Ding to Hongru, the use of go lang type pointers (Poin
公里周日
3D printed this DuPont cable management artifact, and the desktop is no longer messy
MySQL全文索引
浅析JWT安全问题
常用语言图表库总结
编程技术提升
1: bubble sort
RTP
BERT预训练模型(Bidirectional Encoder Representations from Transformers)-原理详解
Attentional Feature Fusion
Technology Sharing | Sending Requests Using cURL
socket实现TCP/IP通信
unix环境编程 第十五章 15.9 共享存储
深度学习--循环神经网络(Recurrent Neural Network)
自启服务mock联调跨域问题