时间戳

首页 > 解决方案 > 最长的子数组，不超过两个相差不超过 1 的不同值

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

问题描述

给定一个整数数组，包含不超过两个不同值的最长子数组的长度是多少，使得不同值的差异不超过 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, 1, 3, 3, 2, 2] -> 长度 = 4; [3,3,2,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;
    }

能有更好的解决方案吗？

标签： javaalgorithm

解决方案

是的。O(n)这是一个有时间和O(1)空间的动态程序。这个想法是，我们可以A[i]通过查看以A[i-1]可能包含较高元素的最佳序列结尾以及A[i-1]以可能包含较低元素结尾的最佳序列来获得序列结尾的答案。

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));
}

推荐阅读