leetcode [#219]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

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 j is at most k.

---

解决方案

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int N = nums.length;
        if(nums == null || N == 0) return false;

        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < nums.length; i++){
            if(i > k) set.remove(nums[i-k-1]);
            if(!set.add(nums[i])) return true;
        }
        return false;
    }
}

---

注意事项

1. 以下方法不稳定，在不同提交时，有时会通过，有时会超时，效率不高，不是好方法：

   import java.util.*;
   
   public class Solution {
       public boolean containsNearbyDuplicate(int[] nums, int k) {
           int N = nums.length;
           if(nums == null || N == 0) return false;
   
           int[] index = new int[N];
           int[] cpy = new int[N];
   
           for(int p = 0; p < N; p++){
               cpy[p] = nums[p];
           }
   
           final Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();
           for(int i = 0; i < N; i++){
               ht.put(i, nums[i]);
           }
   
           List<Integer> v = new ArrayList<Integer>(ht.keySet());
           Collections.sort(v,new Comparator<Object>(){
                       public int compare(Object arg0,Object arg1){
                           return ht.get(arg1) - ht.get(arg0);
                       }
                   }
           );
           int t = N-1;
           for (Integer i : v) {
               index[t--] = i;
           }
           Arrays.sort(nums);
   
           boolean result = false;
           for(int i = 0; i < N-1; i++){
               if(nums[i] - nums[i+1] == 0){
                   if(index[i+1] - index[i] <= k){
                       result = true;
                       break;
                   }
               }
           }
           return result;
       }
   }

2. 解决方案中借鉴了discuss中的优秀回答，这种方法比较巧妙地维护了一个长度为k的HashSet。复杂度为o(n)。