用不同的整数找出最长的子数组

Question

编写一个方法，该方法采用一个整数数组，并返回其最长的具有不同整数的子数组的长度。

例如，对于 [1，2，3，4，2，3]，它应该返回 4。

Answer 1

public static int sizeOfLongestDistinctSubArrayO1(int[] arr) {
    int max = 0;
    Map<Integer, Integer> counts = new HashMap<>();
    int cur = 0;
    int prev = 0;
    for (int i = 0, len = arr.length; i < len; i++) {
        if (counts.containsKey(arr[i])) {
            int j = counts.get(arr[i]);
            max = Math.max(max, cur);
            prev = Math.max(j, prev);
            cur = i - prev;
            counts.put(arr[i], i);
        } else {
            cur++;
            counts.put(arr[i], i);
        }
    }
    return Math.max(max, cur);
}

Answer 2

public int[] getLargestSubArray(int[] array) {
    int length = array.length;
    Set<Integer> set = new HashSet<>();
    int longest = 0;
    int start = 0;

    int longestCurrent = 0;
    int startCurrent = 0;

    int j = 0;
    while (j < length) {
        if (!set.contains(array[j])) {
            set.add(array[j]);
            longestCurrent++;

            if (longestCurrent > longest) {
                longest = longestCurrent;
                start = startCurrent;
            }
            j++;
        } else {
            while (startCurrent < j) {
                longestCurrent--;
                if (array[startCurrent++] == (array[j])) {
                    break;
                }
            }
            set.remove(array[j]);
        }
    }
    int[] longestSubSequence = new int[longest];
    System.arraycopy(array, start, longestSubSequence, 0, longest);
    return longestSubSequence;
}

Answer 3

我使用HashSet跟踪从索引I到索引j的所有元素，并在遍历列表时保持计数器。线性运行时和空间：

public static int longestSubarray(int[] arr) {
    
    int i = 0, j = 1, max = 0, currLength = 1;
    max = Math.max(max, currLength);
    HashSet<Integer> set = new HashSet<Integer>();
    set.add(arr[0]);
    
    while (i < arr.length - 1 && j < arr.length) {
        if (!set.contains(arr[j])) {
            currLength++;
            set.add(arr[j++]);
        }
        else {
            set.remove(arr[i++]);
            currLength--;
        }
    }
    
    return Math.max(currLength, max);
}