具有一致频率的最长子数组的长度

Question

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

示例：

对于 A = [1, 2, 2, 1, 3, 3, 3]，最长一致子数组是 [1, 2, 2, 1, 3, 3]，所以答案是 6。

设 A = [4,5,1,7,5,7,1]，最大子数组为 [5,1,7,5,7,1]，返回长度为 6。

解决这个问题的有效方法是什么？我不确定应该达到什么时间复杂度。

Constraints:
n = array.length
1 < n < 10^5
1 < array[i] < 10^9

我试图在leetcode上找到这样的问题，但最接近的是： https://leetcode.com/problems/length-of-longest-subarray-with-at-most-k-Frequency/description/

这是一个使用二分搜索的潜在解决方案，我尝试过但失败了：

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

Answer 1

O(n^2) 运行时：我使用从每个起点开始增长的窗口并对窗口中的值进行计数，同时跟踪最大计数。而等效的标准是最大计数乘以不同窗口值的数量就是窗口长度。

def solve(A):
  R = 0
  for i in range(len(A)):
    c, C = Counter(), 0
    for r, a in enumerate(A[i:], 1):
      c[a] += 1
      C = max(C, c[a])
      if C * len(c) == r:
        R = max(R, r)
  return R