219. 存在重复元素 II

思路

本题思路很明显是使用双指针+哈希表，具体实现上有几个点可以学习。

首先是在时间几乎无差别（即多一个if语句）的情况下，代码的简洁易懂有时候更为重要。像这题前几个元素的特判，可以不用单独拎一个for循环出来，而是加一个if语句在for循环中，这样便于维护循环不变式。

本题的循环不变式是，i代表右端点，如果i比k大，那么i - k - 1就是将要移除的左端点。如果右端点的值在[i - k, i - 1]内出现过，那么循环结束，返回true。在循环中，我们每次都把右端点的值加入进集合中，并在每个循环开头移除左端点的值。

另外这题可以学到的另一个点是，set的add方法有返回值，如果插入的元素已有则会返回false，这样我们就可以少写一个判断语句。

Code

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