查找最长的子阵列

Question

给定一个整数数组，包含不超过两个不同值的最长子数组的长度是多少，使得非重复值的差异不超过 1？

例：

arr = [0,1,2,1,2,3]

最大的子数组长度为4：[1,2,1,2]。

arr = [1, 1, 1, 3, 3, 2, 2]

最大的子阵列具有长度4:[3，3，2，2]。值1和3相差1以上，因此[1，1，1，3，3]无效。

Answer 1

我认为没有比O（n）更好的解决方案了。

你没有指定任何语言，所以伪代码应该是这样的（我最后写了一个python脚本）：

a = [1, 1, 1, 3, 3, 2, 2]
max_solution_arr = []
cur_sol_arr = []
max_length = 0
cur_len = 0

def min_(a, a_i):
  if len(a) == 0:
      return a_i
  return min(a)

def max_(a, a_i):
  if len(a) == 0:
      return a_i
  return max(a)
for i, a_i in enumerate(a):
    if i == 0:
        cur_sol_arr.append(a_i)
        cur_len += 1
    else:
        if (abs(a[i] - min_(cur_sol_arr, a[i])) <= 1) and (abs(a[i] - max_(cur_sol_arr, a[i])) <= 1):
            # solution extend
            cur_sol_arr.append(a_i)
            cur_len += 1
        else:
            # we need to break, update solution
            if cur_len > max_length:
                max_length = cur_len
                max_solution_arr = cur_sol_arr[:] # make a copy here
                cur_sol_arr = [a_i] # delete
                cur_len = 1
# residual

if cur_len > max_length:
   max_length = cur_len
   max_solution_arr = cur_sol_arr # make a copy here

print(max_solution_arr)

这个想法是，您将保留一个数组，除非不满足条件（

Answer 2

在这段代码中，我们一直查看当前元素之前的元素，检查它们的差是否不大于1，以及该元素是否在我们正在计数的子数组的当前范围内。最后，我们需要增加总数，因为我们需要数组的长度。

Python代码:

def longestSub(arr):
    size = len(arr)
    cMax = cMin = arr[0]
    total = current = 0

    cMax = cMin = arr[0]
    #We will use cMax and cMin to keep track of the range of our current subarray
    for i in range(1,size):
        if(abs(arr[i] - arr[i-1]) <= 1):
            if(arr[i] == cMax or arr[i] == cMin):
                current += 1
            else:
                if(current > total):
                    total = current
                current = 1
                cMax = max(arr[i-1],arr[i])
                cMin = min(arr[i-1],arr[i])
        else:
            if(current > total):
                total = current
            cMin = cMax = arr[i]
    return total+1

if __name__ == "__main__":
    arr = [0, 1, 2, 1, 2, 3]    #length = 4; [1,2,1,2]
    print(longestSub(arr))
    arr = [1, 2, 3, 4, 5]       #length = 2; [1,2]
    print(longestSub(arr))
    arr = [1, 1, 1, 3, 3, 2, 2] #length = 4; [3,3,2,2]
    print(longestSub(arr))

Answer 3

这里是O(1)空间，O(n)时间。通过查看可能包含较高元素的以< code>A[i-1]结尾的最佳序列，以及可能包含较低元素的以< code>A[i-1]结尾的最佳序列，我们可以得到以< code>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));
}