Блог

Проблема: Учитывая массив целых чисел и целое число 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 amp;amp; Math.abs(i-j) <= k) 
            {
                return true;
            }
        }
        
        return false;
    }
  

1. Входной массив не отсортирован, тогда также почему этот код работает, и это принятое решение.
2. Также как подойти к нему, если проблема заключалась в том, что разница была как минимум, а не как максимум?

У вас есть сомнения в правильности этого решения, и вы правы. Это не надежный алгоритм. Если он проходит тестовые случаи, то это просто означает, что тесты недостаточно тщательны.

Вот встречный пример:

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

Код вернется false , в то время как он должен вернуться true .

Совершенно очевидно, что если двоичный поиск выполняется для того, чтобы найти 9, то он не будет найден, так как он будет выглядеть во второй половине массива.