package LeetCode;

import java.util.HashSet;

public class LeetCode219 {

// https://leetcode.com/problems/contains-duplicate-ii/description/

// 时间复杂度: O(n)

// 空间复杂度: O(k)

public boolean containsNearbyDuplicate(int[] nums, int k) {

if(nums == null || nums.length <= 1)

return false;

if(k <= 0)

return false;

// nums = [1,2,3,4,1], k = 3

// nums = [1,2,3,1,2,3], k = 2

HashSet<Integer> record = new HashSet<Integer>();

for(int i = 0 ; i < nums.length; i ++){

if(record.contains(nums[i]))

return true;

record.add(nums[i]);

// 当map的大小大于k+1,那就减去最左边的元素

if(record.size() == k + 1)

record.remove(nums[i-k]);

}

return false;

}

}