最长一致子数组长度求解：高效方法探讨及失败解法分析

给定数组A，若某子数组中所有元素的最大出现次数等于最小出现次数，则该子数组被称为“一致子数组”。请找出并返回A中最长一致子数组的长度。

示例 #

• 示例1：对于数组 A = [1, 2, 2, 1, 3, 3, 3]，最长一致子数组为 [1, 2, 2, 1, 3, 3]，返回长度6。
• 示例2：对于数组 A = [4,5,1,7,5,7,1]，最长一致子数组为 [5,1,7,5,7,1]，返回长度6。

约束条件 #

• n = 数组长度，满足 1 < n < 10^5
• 数组元素满足 1 < array[i] < 10^9

提问 #

求解该问题的高效方法是什么？应瞄准何种时间复杂度？

失败的二分法尝试代码 #

public class Solution {
    public int solve(int[] A) {
        int l = 0, r = A.length, k = 0;
        while (l < r) {
            int m = (l + r) / 2;
            k = verify(A, m);
            if (k == -1) {
                l = m;
            } else {
                r = m;
            }
        }
        return k;
    }
    public int verify(int[] A, int m) {

        for (int i = m; i < A.length; i++) {
            int[] extr = getExt(A, i - m, i);
            if (extr[0] == extr[1]) {
                return m;
            }
        }
        return -1;
    }
    public int[] getExt(int[] A, int l, int r) {
        int[] out = new int[2];
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = l; i < r; i++) {
            freq.put(A[i], freq.getOrDefault(freq.get(A[i]), 0) + 1);
        }
        int max = 0, min = Integer.MAX_VALUE;
        for (int k : freq.values()) {
            max = Math.max(k, max);
            min = Math.min(k, min);
        }
        out[0] = max;
        out[1] = min;
        return out;
    }
}

问题核心拆解 #

一致子数组的本质是：子数组中所有元素的出现次数完全相同。假设子数组包含c种元素，每种元素出现f次，那么子数组长度必然等于c*f。基于这个性质，我们可以针对性设计高效算法。

高效解法思路 #

针对1e5规模的数组，必须将时间复杂度控制在**O(n√n)**级别，这是此类问题的最优可行复杂度。具体分为两种枚举场景：

场景1：枚举元素出现次数f（适用于f ≤ √n） #

对于每个可能的f（从1到√n），遍历数组并维护窗口内元素的出现次数：

• 当某个元素出现次数超过f时，移动左边界收缩窗口，确保窗口内所有元素出现次数不超过f。
• 统计窗口内出现次数恰好等于f的元素种类数count，若count * f == 当前窗口长度，说明该窗口是一致子数组，更新最大长度。

场景2：枚举元素种类数c（适用于c ≤ √n） #

对于每个可能的c（从1到√n），用滑动窗口维护窗口内恰好包含c种元素：

• 当窗口内元素种类超过c时，移动左边界收缩窗口。
• 检查窗口内所有元素的出现次数是否相同，若相同则更新最大长度。

通过这两种场景的枚举，可覆盖所有可能的一致子数组，总时间复杂度为O(n√n)，完全能处理1e5规模的数组。

你的二分法代码问题分析 #

1. 语法逻辑错误：getExt方法中freq.getOrDefault(freq.get(A[i]), 0)参数错误，应改为freq.getOrDefault(A[i], 0)，否则会因freq.get(A[i])返回null触发空指针异常。
2. 时间复杂度爆炸：verify方法中每个窗口都重新统计频率，单轮verify时间复杂度为O(n*m)，结合二分的O(logn)，总复杂度达到O(n²logn)，无法处理1e5规模的数组。
3. 二分边界错误：当前二分逻辑无法正确定位最大长度，正确逻辑应为：找到符合条件的长度时，尝试更大的长度；否则缩小右边界。

内容的提问来源于stack exchange，提问作者Emmanuel Pierre