检查给定数组是否包含彼此距离在 k 以内的重复元素

给定一个可能包含重复项的未排序数组。还给出一个小于数组大小的数字 k。编写一个函数，如果数组包含 k 距离内的重复项，则该函数返回 true。

例如：

输入：k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
输出：假
所有重复项的距离都超过 k。

输入：k = 3, arr[] = {1, 2, 3, 1, 4, 5}
输出：真
1 在距离 3 处重复。

输入：k = 3，arr[] = {1, 2, 3, 4, 5}
输出：假

输入：k = 3，arr[] = {1, 2, 3, 4, 4}
输出：真

一个简单的解决方案是运行两个循环

外部循环选择每个元素“arr”作为起始元素，
内部循环比较“arr”k 距离内的所有元素。

该解决方案的时间复杂度为 O(k * n)。
Java
public class GFG
{

/* Java program to Check if a given array contains
   duplicate elements within k distance from each other */
public static boolean
   checkDuplicatesWithinK(int[] arr, int n, int k)
{

   // traversing the input array
   for (int i = 0; i < n; i++) {
   int j = i + 1;
   int range = k;
   // 在下 k-1 个元素中搜索其
   //是否存在重复元素
   while (range > 0 && j < n) {
       if (arr[i] == arr[j]) {
       return true;
       }
       j++;
       range--;
   }
   }
   return false;
}

// 测试上述方法的驱动程序方法
public static void main(String[] args)
{
   int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
   int n = arr.length;
   if (checkDuplicatesWithinK(arr, n, 3)) {
   System.out.print("Yes");
   }
   else {
   System.out.print("No");
   }
}
}

Python：
# Python3 program to Check if a given array contains duplicate
# elements within k distance from each other
def checkDuplicatesWithinK(arr, n, k):

   # 遍历输入数组
   for i in range(n):
       j = i + 1
       range_ = k

       # 在下 k-1 个元素中查找是否存在重复
      #
       while (range_ > 0 and j < n):
           if (arr[i] == arr[j]):
               return True
           j += 1
           range_ -= 1

   return False

# Driver method to test above method

arr = [10, 5, 3, 4, 3, 5, 6]
n = len(arr)
if (checkDuplicatesWithinK(arr, n, 3) == True):
   print("Yes")
else:
   print("No")

C#

/* C# program to Check if a given
array contains duplicate elements
within k distance from each other */
using System;
using System.Collections.Generic;

class GFG {
   static bool checkDuplicatesWithinK(int[] arr, int n,
                                   int k)
   {
       // traversing the input array
       for (int i = 0; i < n; i++) {
           int j = i + 1;
           int range = k;
           // searching in next k-1 elements if its
           // duplicate is present or not
           while (range > 0 && j < n) {
               if (arr[i] == arr[j])
                   return true;
               j++;
               range--;
           }
       }
       return false;
   }

   // Driver code
   public static void Main(String[] args)
   {
       int[] arr = { 10, 5, 3, 4, 3, 5, 6 };
       int n = arr.Length;
       if (checkDuplicatesWithinK(arr, n, 3))
           Console.WriteLine("Yes");
       else
           Console.WriteLine("No");
   }
}

Javascript

class GFG
{
   // javascript program to Check if a given array contains
   //   duplicate elements within k distance from each other
   static checkDuplicatesWithinK(arr, n, k)
   {
       // traversing the input array
       for (var i=0; i < n; i++)
       {
           var j = i + 1;
           var range = k;
           //在下 k-1 个元素中搜索，如果其
// 是否存在重复
           while (range > 0 && j < n)
           {
               if (arr[i] == arr[j])
               {
                   return true;
               }
               j++;
               range--;
           }
       }
       return false;
   }

   // Driver method to test above method
   static main(args)
   {
       var arr = [10, 5, 3, 4, 3, 5, 6];
       var n = arr.length;
       if (GFG.checkDuplicatesWithinK(arr, n, 3))
       {
           console.log("Yes");
       }
       else
       {
           console.log("No");
       }
   }
}
GFG.main([]);