LeetCode算法题-Contains Duplicate II(Java实现)

LeetCode算法题-Contains Duplicate II(Java实现)

这是悦乐书的第193次更新,第197篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第53题(顺位题号是219)。给定整数数组和整数k,找出数组中是否存在两个不同的索引i和j,使得nums [i] = nums [j]并且i和j之间的绝对差值小于等于k。例如:

输入:nums = [1,2,3,1],k = 3
输出:true

输入:nums = [1,0,1,1],k = 1
输出:true

输入:nums = [1,2,3,1,2,3],k = 2
输出:false

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

利用hashMap,依次遍历数组元素,如果当前元素不存在就put进map,如果存在,则说明具有重复元素,然后获取当前索引与此元素在map中的索引value值的绝对值,判断其是否小于等于k,如果满足,则返回true。

此解法因为用到了map.containsKey()方法,所以时间复杂度最好的情况是O(n),最坏的情况是O(n^2),空间复杂度是O(n)。

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<nums.length; i++) {
        if (map.containsKey(nums[i]) && Math.abs(i-map.get(nums[i])) <= k) {
            return true;
        } else {
            map.put(nums[i], i);
        }
    }
    return false;
}


03 第二种解法

如果满足题目的条件,nums[i] = nums[j],并且j-i <= k,那么只要nums[i]等于nums[i+1]至nums[i+k]之间的任意一个,即可返回true。使用两层for循环,外层控制从1到k,内层遍历数组元素,如果外层指针加上内层指针小于数组大小,并且两指针对应的元素相等,则返回true。

此解法的时间复杂度是O(k*n),最好的情况是O(n),最坏的情况是O(n^2),空间复杂度是O(1)。此解法会超时

public boolean containsNearbyDuplicate2(int[] nums, int k) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    for (int i=1; i<= k; i++) {
        for (int j=0; j<nums.length; j++) {
            if (j+i < nums.length && nums[j] == nums[j+i]) {
                return true;
            }
        }
    }
    return false;
}


04 第三种解法

此解法与上面第二种解法的思路一致,不过是将内外层循环换了位置,并且内层循环判断nums[i]和nums[j]相等时,对于指针的范围做了调整,从数组长度、i+1+k之间取最小值。

public boolean containsNearbyDuplicate3(int[] nums, int k) {
    if (nums == null || nums.length <= 1) {
        return false;
    }
    for (int i=0;i < nums.length; i++) {
        for (int j=i+1; j<Math.min(nums.length, i+1+k); j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

05 第四种解法

利用HashSet。此解法的代码和昨天的那道题没多大区别,只不过是在循环判断true或false的前面,加多了一个判断,如果当前的指针i大于k,那么就将HashSet中的nums[i - k - 1]元素删除,即当i>k的时候,将HashSet从第1一个元素开始移除,表示前k个元素已经不符合题目的条件了,并且随着循环继续,会依次删除不符合的元素。

public boolean containsNearbyDuplicate4(int[] nums, int k) {
    if (nums == null || nums.length <= 1) {
        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;
}


06 第五种解法

使用双指针。循环内判断true或false的地方,如果两指针不相等,并且其各自所指向的元素相等,则返回true。第二个判断是移动两个指针的关键,两个指针初始值都是0,如果两指针的差小于k,则其中做一个指针加1,否则另外一个指针加1,即判断相隔小于k位之间的元素是否相等。

public boolean containsNearbyDuplicate5(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k == 0) {
        return false;
    }
    int p1 = 0;
    int p2 = 0;
    while (p1 < nums.length) {
        if (nums[p1] == nums[p2] && p1 != p2) {
            return true;
        }
        if (p2 - p1 < k && p2 < nums.length - 1) {
            p2++;
        } else {
            p1++;
        }
    }
    return false;
}


07 小结

算法专题目前已连续日更超过一个月,算法题文章53+篇,