LeetCode(219): Contains Duplicate II

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.

题意：对于一个给定的数组，判断是否存在重复的元素；对于存在重复的元素的定义是在一个给定的k长度内，该数组任意相邻k个元素之间不存在重复的值。

思路：对于此题采用滑动窗口的方法来进行求解，滑动窗口的大小为k，用HashSet来存储该窗口内的值，同时用来判断窗口内的数字是否重复出现。同时使用两个指针left和right标记窗口的两端，刚开始值都为0，然后对right不断加1，将right指向的值加入HashSet中去，判断是否出现重复值，直到righ-left>k，left加1，并移除相应的元素。如果到数组末尾没有发现重复的值则返回false。

代码：

public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> Num = new HashSet<Integer>();
        int left=0,right=0;
        if(nums.length==0)return false;
        for(int i=0;i<nums.length;i++){
            if(!Num.contains(nums[i])){
                Num.add(nums[i]);
                right++;
            }else return true;
            if(right - left > k){
                Num.remove(nums[left]);
                left++;
            }
        }
        return false;
    }

LeetCode(219): Contains Duplicate II

原文：http://www.cnblogs.com/Lewisr/p/5111553.html