【Leetcode】 219. Contains Duplicate II

Description

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 absolute difference between i and j is at most k.

Solution

public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int len = nums.length;
        if (len == 0 || k == 0) {
            return false;
        }
        for (int i = 0; i < len; i++) {
            List<Integer> l = new ArrayList<>();
            if (map.containsKey(nums[i])) {
                l = map.get(nums[i]);
            }
            l.add(i);
            map.put(nums[i], l);
        }
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            if (entry.getValue().size() != 1) {
                List<Integer> list = entry.getValue();
                for (int j =  0; j < list.size() - 1; j++) {
                    if (list.get(j + 1) - list.get(j) <= k) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

Analyse

这里就是简单的用了一个map，用list存储相同数字的位数，那么就可以进行判断，复杂度到了O(n ^ 2)。

Optimization

First

public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        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;
    }

Analyse

这个方法不错，主要利用了set.add方法的返回值，而且用set构造了一个k大小的滑动窗口，感觉很赞，时间复杂度O(n)。

Second

public boolean containsNearbyDuplicate(int[] nums, int k) {
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            if (map.containsKey(nums[i])) {
                if (i - map.get(nums[i]) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }

Analyse

这个map比我用的好太多，直接在map生成过程中判定，很简单。