arrays - 219. Contains Duplicate II - 为什么使用二分查找的解决方案适用于未排序的数组？

Question

问题：给定一个整数数组和一个整数 k，找出数组中是否有两个不同的索引 i 和 j，使得 nums[i] = nums[j] 并且 i 和 j 之间的绝对差最多为 k。

示例 1：

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

我使用 HashSet(java) 解决了它。

但是当我浏览下面提交的一些解决方案时，引起了我的注意：

 public boolean containsNearbyDuplicate(int[] nums, int k) 
    {
        int len = nums.length;
        
        for(int i=0; i<len; i++) 
        {
            int j = Arrays.binarySearch(nums, nums[i]);// Y this works as array is not sorted. Copied sol from submitted solution
            if(i != j && Math.abs(i-j) <= k) 
            {
                return true;
            }
        }
        
        return false;
    }

1. 输入数组未排序，这也是为什么此代码有效并且它是公认的解决方案。
2. 如果问题是至少而不是最多的差异，那么如何解决它？

标签： arraysalgorithmdata-structuresbinary-search

Answer 1

你怀疑这个解决方案的正确性，你是对的。这不是一个健全的算法。如果它通过了测试用例，那就意味着测试不够彻底。

这是一个反例：

[9, 9, 1, 2, 3]
1

代码将返回false，而它应该返回true。

很明显，如果执行二进制搜索以找到 9，将不会找到它，因为它会查找数组的后半部分。