LeetCode解题记录（十五）

数组篇 （简单）十五
219. 存在重复元素 II
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。(不大于k)
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true

方法一：暴力循环

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for(int i=0;i<nums.length;i++)
            for(int j=(i+1);j<nums.length;j++)
                if(nums[i]==nums[j]&&Math.abs(i-j)<=k)
                    return true;
        return false;
    }
}

但是暴力循环同样有高下之分，题解的暴力循环就要比我的无脑循环更省时,利用一个滑动窗口。
注意j的边界，最大循环至j<i，因为如果存在下标比i更大的符合要求的元素，那么i迟早会循环到，而不需要j去判断

public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}

方法二：哈希表查询,空间换时间

class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i)
    {
        if (set.contains(nums[i])) 
            return true;
        set.add(nums[i]);
        if (set.size() > k)               当哈希表的长度比K还大时，需要把之前的数据一个个删掉，
            set.remove(nums[i - k]);	  因为有可能存在相同数字，但下标已经超过了K
    }
        return false;
}
}