Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Ideological reference ： Maintain a length of k Of window, Check whether the difference between the new value and all the values in the original window is less than or equal to each time t Of . If you use two for The loop will time out O(nk). Use treeset( backed by binary search tree) Of subSet function , You can quickly search . The complexity is O(n logk)

The code is as follows ：

import java.util.SortedSet;

public class Solution {

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

if(k<1 || t<0 ||nums==null ||nums.length<2) return false;

SortedSet<Long>set=new TreeSet<>();

int len=nums.length;

for(int i=0;i<len;i++){

SortedSet<Long>subSet=set.subSet((long)nums[i]-t,(long)nums[i]+t+1);

if(!subSet.isEmpty()) return true;

if(i>=k)

set.remove((long)nums[i-k]);

set.add((long)nums[i]);

}

return false;

}

}

Running results ：

(medium)LeetCode 220.Contains Duplicate III More articles about

  1. [LeetCode] 220. Contains Duplicate III Contains repeating elements III

    Given an array of integers, find out whether there are two distinct indices i and j in the array suc ...

  2. Java for LeetCode 220 Contains Duplicate III

    Given an array of integers, find out whether there are two distinct indices i and j in the array suc ...

  3. [Leetcode] 220. Contains Duplicate III

    Given an array of integers, find out whether there are two distinct indices i and j in the array suc ...

  4. 【medium】220. Contains Duplicate III

    Because we have to consider the timeout problem , So although it's simple for Circulation can also do , But use map And so on . Given an array of integers, find out whether there ar ...

  5. LeetCode 220. Contains Duplicate III （ Dividing barrel method ）

    Given an array of integers, find out whether there are two distinct indices i and j in the array suc ...

  6. 【LeetCode】220. Contains Duplicate III

    subject : Given an array of integers, find out whether there are two distinct indices i and j in the array ...

  7. 220. Contains Duplicate III

    subject : Given an array of integers, find out whether there are two distinct indices i and j in the array ...

  8. 220 Contains Duplicate III Repetition exists III

    Given an array of integers , Determine if there are two different indexes in the array i and j, send nums [i] and nums [j] The maximum absolute difference of is t, also i and j The maximum absolute difference between them is k. See :https://le ...

  9. 220. Contains Duplicate III Array pointer difference k Numerical difference t

    ［ Copy questions ］: Given an array of integers, find out whether there are two distinct indices i and j in the arr ...

Random recommendation

  1. mysqldump Implementation principle of

    about MySQL Backup of , It can be divided into the following two types : 1. Cold standby 2. Hot standby among , Cold standby , seeing the name of a thing one thinks of its function , Just turn off the database , Use the operating system command to copy database related files . Hot standby refers to online hot standby , That is, without shutting down the database , The database is ...

  2. turn ：C/C++ in , An empty array 、 Empty class 、 Class empty array parsing and its role

    from :http://blog.sina.com.cn/s/blog_93b45b0f01015s95.html We often encounter these problems : (1)C++ Define an empty class in , They know the size of it (sizeof) As many ...

  3. RobotFramework Key words for automated testing framework （ 5、 ... and ）

    1.1.1        Run Keyword If Use of judgment Run Keyword If Is a common keyword used to make logical judgment , It means that if a certain judgment condition is satisfied , Then the keyword is executed , We are right. list3 in ...

  4. use c Language to create a two-way circular list

    As a C Developer , No matter in the written examination of job hunting , Or in engineering projects , It's going to work c Language to create a two-way circular list . This is also understanding and using c A basic skill of pointer . #include<...>// The header file is omitted typedef ...

  5. Python—— Crack polar sliding captcha

    Polar slide verification code The above picture is the most typical one, which belongs to the extreme sliding certification , Check the official website :http://www.geetest.com/. Now the verification code has been updated to 3.0 edition , By 2017 year 7 There are 160000 in the world this month ...

  6. 9 The best JavaScript Compression tool

    Pruning is a technique for removing unnecessary characters from the source code to make it look simple and neat . This technique is also known as code compression and minimization . ad locum , We have collected for you 10 The best JavaScript The compression tool will help you remove unnecessary spaces , A newline , Comment on , ...

  7. front end VUE frame

    One . What is? VUE?  It's a way to build the user interface JAVASCRIPt frame   vue Don't care what tags are on your page , It operates on variables or properties Why use VUE? When the front and rear ends are separated , The back end only returns json data , No more ...

  8. MySQL DROP DB or TABLE With the help of SQL Thread Fast application binlog Recovery plan

    [ problem ] Suppose there's such a scenario , Misoperation DROP DB or TABLE, The normal recovery operation is to restore a full backup , And use mysqlbinlog Append to drop Position before operation . If you need to recover binlog We only want to recover ...

  9. c# Generate rsa Public and private keys

    c# Generate rsa Class library of public key and private key , Including encryption and decryption , It can be used on websites and winform project Source code address : http://download.csdn.net/detail/jine515073/8383809

  10. Project use protobuf

    In the mutual system, data communication or data exchange can use protobuf, He compared json.xml The amount of data is smaller . In addition, because the message has to be written separately .proto file , To generate code for each platform , So it's also friendly for cross platform communication . One . Use ...