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
- [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 ...
- 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 ...
- [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 ...
- 【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 ...
- 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 ...
- 【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 ...
- 220. Contains Duplicate III
subject : Given an array of integers, find out whether there are two distinct indices i and j in the array ...
- 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 ...
- 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
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 , ...
- 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 ...
- 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 ...
- 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
- 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 ...