ContainsDuplicateIIOPT [source code]

public class ContainsDuplicateIIOPT {
static
/******************************************************************************/
public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (k == 35000) return false;
        int size = nums.length;
        if (k >= size) {
            return containsNearbyDuplicate(nums);
        }
        if (k > 0 && size > 1) {
            int i = 0;
            while (i < size - k) {
                if (containsNearbyDuplicate(Arrays.copyOfRange(nums, i, i + k + 1)))
                    return true;
                i++;
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums) {
        int size = nums.length;
        Arrays.sort(nums);
        for (int i = 1; i < size; i++) {
            if (nums[i - 1] == nums[i]) {
                return true;
            }
        }
        return false;
    }
}
/******************************************************************************/

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

这个是 submission 最优解, 让人难以置信的0(99);

我操这个果然还真的是sliding window来做的. 我当时几乎都想写一个这样的代码了, 不过后来想想 duplicate 实际上也不好处理;
他这个其实worst case 的速度并不好, 因为他是用了排序的. 总的来说这个解还是利用了一个HashMap 的 overhead 问题的意思吧.

另外严格来说这个算法都不算是sliding window, 这个就跟最普通的substring search一样, 最基本的slide, 没有什么特别的技术含量的;

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