最长的子数组，不超过两个不同的值，其差值不超过1

Question

给定一个整数数组，包含不超过两个不同值的最长子数组的长度是多少，这样不同值的差异不超过1

例如：

arr=[0,1,2,1,2,3]->长度=4；[1,2,1,2]

arr=[1,2,3,4,5]->长度=2；[1，2]

arr=[1,1,3,2,2]->长度=4；[3,3,2]

我有这样的代码

public static int longestSubarray(List<Integer> arr) {
int max = 0;
Set<Integer> set = new HashSet<>();
int i = 0;
int j = 1;
while (i < arr.size() - 1) {
set.add(arr.get(i));
while (j < arr.size() && Math.abs(arr.get(i) - arr.get(j)) < 2) {
if (!set.contains(arr.get(j))) {
if (set.size() == 2) {
break;
} else {
set.add(arr.get(j));
}
}
++j;
}
max = Math.max(max, j - i);
j = ++i + 1;
set.clear();
}
return max;
}

有更好的解决方案吗？

Answer 1

是。这是一个具有O(n)时间和O(1)空间的动态程序。其思想是，我们可以通过观察可能包括较高元素的、在A[i-1]处结束的最佳序列和可能包括较低元素的在A[i-1]处结束的最优序列来获得在A[i]处结束的序列的答案。

JavaScript代码：

function f(A){
if (A.length < 2)
return A.length;

let best = 1;
let bestLower = 1;
let bestHigher = 1;

for (let i=1; i<A.length; i++){
if (A[i] == A[i-1]){
bestLower = bestLower + 1;
bestHigher = bestHigher + 1;

} else if (A[i] - 1 == A[i-1]){
bestLower = 1 + bestHigher;
bestHigher = 1;

} else if (A[i] + 1 == A[i-1]){
bestHigher = 1 + bestLower;
bestLower = 1;

} else {
bestLower = 1;
bestHigher = 1;
}
best = Math.max(best, bestLower, bestHigher);
}

return best;
}
arrays = [
[0, 1, 2, 1, 2, 3], // length = 4; [1,2,1,2]
[1, 2, 3, 4, 5], // length = 2; [1,2]
[1, 1, 1, 3, 3, 2, 2] // length = 4; [3,3,2,2]
];
for (let arr of arrays){
console.log(JSON.stringify(arr));
console.log(f(arr));
}

Answer 2

C#代码：

using System.IO;
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
List<int> arr = new List<int>(){ 0, 1, 2, 1, 2, 3};
List<int> set = new List<int>(); 
int n = arr.Count;
int max = 1;
int i,j;
for(i=0 ; i<n-1; i++)
{
set.Add(arr[i]);
for(j=i+1; j<n; )
{
if(Math.Abs(arr[i]-arr[j])<2)
{
if(!set.Contains(arr[j]))
{
if(set.Count == 2)
break;
else
set.Add(arr[j]);
}  
}
else
break;
j++;
}
max = Math.Max(max,j-i);
set.Clear();
}
Console.WriteLine(max); 
}
}

Answer 3

请参阅本GFG文章然后用1个代替X

链接：https://www.geeksforgeeks.org/longest-subarray-in-which-absolute-difference-between-any-two-element-is-not-greater-than-x/

Answer 4

具有O(n(时间复杂性的Java解决方案

静态int解决方案(List-arr(｛

int subArrStart = 0;
int changedSubArrStart = 0;
int longSubArrayLen = 0;
int currSubArrayLen = 0;
for (int i = 0; i < arr.size(); i++) {
if (arr.get(subArrStart) == arr.get(i)) {
currSubArrayLen++;
} else if (Math.abs(arr.get(subArrStart) - arr.get(i)) == 1) {
if (subArrStart == changedSubArrStart) {
changedSubArrStart = i;
}
currSubArrayLen++;
} else if (Math.abs(arr.get(changedSubArrStart) - arr.get(i)) == 1) {
subArrStart = changedSubArrStart;
currSubArrayLen = i - subArrStart + 1;
} else {
subArrStart = i;
changedSubArrStart = i;
currSubArrayLen = 1;
}
longSubArrayLen = Math.max(longSubArrayLen, currSubArrayLen);
}
return longSubArrayLen;
}