最长的子数组，任意两个不同值之间的差值恰好为K _数据结构

本文概述

C ++
Java
Python3
C#

给定一个长度为N且整数为K的数组arr[]，任务是找到任意两个不同值之间的差值为K的最长子数组。打印得到的最长子数组的长度。否则，如果没有这样的子数组，则打印-1。
例子：

输入：arr[] = {0, 0, 1, 1, 3, 3, 3}, K = 1
输出：4
说明：
子数组{0, 0, 1, 1}是仅有的两个子数组之间有差异的子数组等于K(= 1)的不同值。因此, 长度等于4。
输入：arr[] = {5, 7, 1, 1, 2, 2, 4, 4, 4, 5, 5, 4, 5, 8, 9}, K = 1
输出：7说明：
子数组{1、1、2}, {4、4、4、5、5、4、5}和{8、9}是仅有的两个等于K(= 1)的不同值之间具有差异的子数组。其中最长的子数组是{4, 4, 4, 5, 5, 4, 5}。因此, 长度为7。

简单的方法：

一个简单的解决方案是一一考虑所有子数组, 然后查找仅包含两个不同值的子数组, 这两个值之间的差为K。不断更新获得的子数组的最大长度。
最后打印获得的最大长度。

时间复杂度：O(N^3)
辅助空间：O(N)
高效方法：
可以观察到，对于任意两个元素之差为K的元素所组成的子数组，该子数组必须只有两个不同的值。因此，可以进一步优化上述方法，使用set寻找只有两个不同值且差k的最长子数组，按照以下步骤解决问题:

从数组的起始索引开始第一个子数组。
将该元素插入集合。继续下一个元素, 并检查该元素是否与前一个元素相同或绝对差为K。
如果是这样, 则将该元素插入集合, 然后继续增加子数组的长度。一旦找到第三个不同的元素, 请将当前子数组的长度与子数组的最大长度进行比较, 然后进行相应更新。
将获得的新元素更新到集合中, 然后重复上述步骤。
遍历整个数组后, 打印获得的最大长度。

下面是上述方法的实现：
C ++

//C++ implementation to find the //longest subarray consisting of //only two values with difference K #include < bits/stdc++.h> using namespace std; //Function to return the length //of the longest sub-array int longestSubarray( int arr[], int n, int k) { int i, j, Max = 1; //Initialize set set< int> s; for (i = 0; i < n - 1; i++) { //Store 1st element of //sub-array into set s.insert(arr[i]); for (j = i + 1; j < n; j++) { //Check absolute difference //between two elements if ( abs (arr[i] - arr[j]) == 0 || abs (arr[i] - arr[j]) == k) { //If the new element is not //present in the set if (!s.count(arr[j])) { //If the set contains //two elements if (s.size() == 2) break ; //Otherwise else s.insert(arr[j]); } } else break ; } if (s.size() == 2) { //Update the maximum //length Max = max(Max, j - i); //Remove the set //elements s.clear(); } else s.clear(); } return Max; } //Driver Code int main() { int arr[] = { 1, 0, 2, 2, 5, 5, 5 }; int N = sizeof (arr) /sizeof (arr[0]); int K = 1; int length = longestSubarray( arr, N, K); if (length == 1) cout < < -1; else cout < < length; return 0; }

Java

//Java implementation to find the //longest subarray consisting of //only two values with difference K import java.util.*; class GFG{ //Function to return the length //of the longest sub-array static int longestSubarray( int arr[], int n, int k) { int i, j, Max = 1 ; //Initialize set HashSet< Integer> s = new HashSet< Integer> (); for (i = 0 ; i < n - 1 ; i++) {//Store 1st element of //sub-array into set s.add(arr[i]); for (j = i + 1 ; j < n; j++) {//Check absolute difference //between two elements if (Math.abs(arr[i] - arr[j]) == 0 || Math.abs(arr[i] - arr[j]) == k) {//If the new element is not //present in the set if (!s.contains(arr[j])) {//If the set contains //two elements if (s.size() == 2 ) break ; //Otherwise else s.add(arr[j]); } } else break ; } if (s.size() == 2 ) {//Update the maximum //length Max = Math.max(Max, j - i); //Remove the set //elements s.clear(); } else s.clear(); } return Max; } //Driver Code public static void main(String[] args) { int arr[] = { 1 , 0 , 2 , 2 , 5 , 5 , 5 }; int N = arr.length; int K = 1 ; int length = longestSubarray(arr, N, K); if (length == 1 ) System.out.print(- 1 ); else System.out.print(length); } } //This code is contributed by Princi Singh

Python3

# Python3 implementation to find the # longest subarray consisting of # only two valueswith difference K # Function to return the length # of the longest sub-array def longestSubarray (arr, n, k): Max = 1 # Initialize set s = set () for i in range (n - 1 ): # Store 1st element of # sub-array into set s.add(arr[i]) for j in range (i + 1 , n):# Check absolute difference # between two elements if ( abs (arr[i] - arr[j]) = = 0 or abs (arr[i] - arr[j]) = = k): # If the new element is not # present in the set if ( not arr[j] in s): # If the set contains # two elements if ( len (s) = = 2 ): break # Otherwise else : s.add(arr[j])else : break if ( len (s) = = 2 ): # Update the maximum length Max = max ( Max , j - i) # Remove the set elements s.clear() else : s.clear() return Max # Driver Code if __name__ = = '__main__' :arr = [ 1 , 0 , 2 , 2 , 5 , 5 , 5 ] N = len (arr) K = 1 length = longestSubarray(arr, N, K) if (length = = 1 ): print ( "-1" ) else : print (length) # This code is contributed by himanshu77

//C# implementation to find the //longest subarray consisting of //only two values with difference K using System; using System.Collections.Generic; class GFG{ //Function to return the length //of the longest sub-array static int longestSubarray( int []arr, int n, int k) { int i, j, Max = 1; //Initialize set HashSet< int> s = new HashSet< int> (); for (i = 0; i < n - 1; i++) {//Store 1st element of //sub-array into set s.Add(arr[i]); for (j = i + 1; j < n; j++) {//Check absolute difference //between two elements if (Math.Abs(arr[i] - arr[j]) == 0 || Math.Abs(arr[i] - arr[j]) == k) {//If the new element is not //present in the set if (!s.Contains(arr[j])) {//If the set contains //two elements if (s.Count == 2) break ; //Otherwise else s.Add(arr[j]); } } else break ; } if (s.Count == 2) {//Update the maximum //length Max = Math.Max(Max, j - i); //Remove the set //elements s.Clear(); } else s.Clear(); } return Max; } //Driver Code public static void Main(String[] args) { int []arr = { 1, 0, 2, 2, 5, 5, 5 }; int N = arr.Length; int K = 1; int length = longestSubarray(arr, N, K); if (length == 1) Console.Write(-1); else Console.Write(length); } } //This code is contributed by Princi Singh

输出如下：