LeetCode-Contains Duplicate II

待我称王封你为后i 2022-08-09 05:09 3阅读 0赞

*  **Problem:**

> > Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums\[i\] = nums\[j\] and the difference between i and jis at most k.(i和j的差最多是k)

*  **analysis:**

> > 利用HashMap比较容易想到，但是利用HashSet不好做，需要利用滑动游标标记，一旦end-start>k则删除HashSet的nums\[start\]项

*  **anwser:**

> > 1 
> 
> >     public class Solution {
> >         public boolean containsNearbyDuplicate(int[] nums, int k) {
> >             Map<Integer,Integer> map= new HashMap<Integer,Integer>();
> >             int j;
> >             for(int i=0;i<nums.length;i++){
> >                 if(map.containsKey(nums[i])){
> >                   j = map.get(nums[i]); 
> >                   if((i-j)<=k) return true;
> >                   else {
> >                       map.remove(nums[j]);
> >                       map.put(nums[i],i);
> >                   }
> >                 }
> >                 else map.put(nums[i],i);
> >             }
> >             return false;
> >         }
> >     }
> > 
> >   
> >   
> > 
> 
> >   
> > 
> > 
> > 2 
> > 
> >     public class Solution {
> >         public boolean containsNearbyDuplicate(int[] nums, int k) {
> >              Set<Integer> appearedNum = new HashSet<Integer>();  
> >             int start = 0, end = 0;  
> >             for(int i = 0; i < nums.length; i++){  
> >                 if(!appearedNum.contains(nums[i])){  
> >                     appearedNum.add(nums[i]);  
> >                     end++;  
> >                 } else return true;  
> >                 if(end - start  > k) {  
> >                     appearedNum.remove(nums[start]);  
> >                     start++;  
> >                 }  
> >             }  
> >             return false;  
> >         }
> >     }
> > 
> >   
> >   
> >