写点什么

【LeetCode】存在重复元素 III Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 04 月 17 日

题目描述

给你一个整数数组 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
复制代码


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/problems/contains-duplicate-iii

代码

public class DayCode {    public static void main(String[] args) {        int[] nums = new int[]{1, 2, 3, 1};        int k = 3, t = 0;
boolean ans = new DayCode().containsNearbyAlmostDuplicate(nums, k, t); System.out.println("ans is " + ans); }
/** * * @param nums * @param k * @param t * @return */ public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { int n = nums.length; TreeSet<Long> treeSet = new TreeSet<>(); for (int i = 0; i < n; i++) { Long u = nums[i] * 1L; Long l = treeSet.floor(u); Long r = treeSet.ceiling(u); if (l != null && u - l <= t) { return true; } if (r != null && r - u <= t) { return true; } treeSet.add(u); if (i >= k) { treeSet.remove(nums[i - k] * 1L); } }
return false; }}
复制代码

总结

  • 我们使用了 TreeSet 这种结构实现代码。TreeSet 的官方介绍如下:


A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
复制代码


  • 坚持每日一题,加油!

发布于: 2021 年 04 月 17 日阅读数: 13
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】存在重复元素 III Java题解