219.包含重复II-为什么使用二进制搜索的解决方案适用于未排序的数组

Question

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

示例1:

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

我使用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. 此外，如果问题是至少而不是最多的差异，该如何处理

Answer 1

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

这里有一个反例：

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

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

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