leetcode 220. Contains Duplicate III 存在重复元素 III(困难)
一、题目大意
给你一个整数数组 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著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
这道题关注与不同值之间的关系,有两个限制条件,两个数字的坐标差不能大于 k,值差不能大于 t。还是用 map 结构来记录值和下标的映射。这里定义两上变量 i 和 j,开始都指向 0,然后 i 开始向右遍历数组,如果 i 和 j 之差大于 k,且 map 中有 nums[j],则删除并 j+1,这样保证了 map 中所有的数的下标之差都不大于 k,然后我们检查如果有值差小于等于则返回 true。遍历最后返回 false。
三、解题方法
3.1 Java 实现
四、总结小记
2022/10/13 老板是公司的支柱,公司的支柱是全身心投入到公司的人
版权声明: 本文为 InfoQ 作者【okokabcd】的原创文章。
原文链接:【http://xie.infoq.cn/article/2d0ebf9ad3755fbc861e348bf】。文章转载请联系作者。
评论