ContainsDuplicateII [source code]

public class ContainsDuplicateII {
static
/******************************************************************************/
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k <= 0 || nums.length == 0) return false;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i  = 0; i < nums.length; i++) {
            Integer index = map.get(nums[i]);
            if (index == null) {
                map.put(nums[i], i);
            } else {
                if (i - index <= k) return true;
                map.put(nums[i], i);
            }
        }
        return false;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ContainsDuplicateII.Solution tester = new ContainsDuplicateII.Solution();
    }
}

这题的笨办法是什么? 可以直接排序, 然后直接找就行了;
那么在这个基础上的优化, 肯定是想要做到O(N); //看错题目了, 我还以为是找value差距在 k 以内的;

看懂题目之后这个题目还是比较简单的, 就是一个2sum 的简化版本, 最后的速度是19ms (50%).
另外注意这个算法你要及时的更新保证 map 里面存的是rightmost. 因为你map 里面的历史信息是给下一个 entry 用的, 对于下一个 entry 有用的就是该 entry 向左走的第一个, 也就是the rightmost one in the history;

历史信息算法, 就是考虑你走到某一个位置的时候, 什么样的信息将有利于你对过往历史做出全面的判断;

这个是 discussion 里面 map 算法的一个简化写法:

public class Solution {  
    public boolean containsNearbyDuplicate(int[] nums, int k) {  
        Map<Integer, Integer> index = new HashMap<>();  
        for (int i = 0; i < nums.length; i++) {  
            if (i - k <= index.getOrDefault(nums[i], -k - 1))  
                return true;  
            index.put(nums[i], i);  
        }  
        return false;  
    }  
}

感觉这个题目好像sliding window可以做的样子;

这个是 editorial 最优解:

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) {  
            set.remove(nums[i - k]);  
        }  
    }  
    return false;  
}

这个做法的要诀就是原来 set 的 size 是可以控制的, 这个我本来还真的不知道; 严格来说这个其实做的也是一个类似sliding window的工作? 只不过用 set 来表达这个 window;

这个是一个更 concise 的写法:

public boolean containsNearbyDuplicate(int[] nums, int k) {  
        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;  
 }

这个算法有明确的加人和踢人的操作, 所以是一个非常典型的sliding window算法;

Problem 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.

Difficulty:Easy
Total Accepted:112.2K
Total Submissions:348.4K
Contributor: LeetCode
Companies
palantir airbnb
Related Topics
array hash table
Similar Questions
Contains Duplicate Contains Duplicate III