2015年11月3日星期二

Leetcode 219 Contains Duplicate II

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.
Solution 1:  Use hash table and slide window
 public class Solution {  
   public boolean containsNearbyDuplicate(int[] nums, int k) {  
     Set<Integer> set=new HashSet<>();  
     int i=0;  
     for (int j=0; j<nums.length; j++) {  
       if (j-i>k) set.remove(nums[i++]);  
       if (set.contains(nums[j])) return true;  
       set.add(nums[j]);  
     }  
     return false;  
   }  
 }  

没有评论:

发表评论