• 用 map 来保存 $s[i]$
• 时间复杂度：$O(n \times log(n))$
• 如果使用 unordered_map，就是 $O(n)$

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int>& a) {
    int n = a.size(), ans = 0;
    unordered_map<int, int> q;

	// q[i] = j: 前缀奇偶数之差为 y 的最小下标为 j
    q[0] = 0;
    for (int i = 1, s = 0; i <= n; i++) {
        s += (a[i - 1] ? 1 : -1);

		// 两个前缀和相减, 就可以得到一段连续子数组
        if (q.count(s)) ans = max(ans, i - q[s]);
        else q[s] = i;
    }
    return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<int> a(n);
		for (int i = 0; i < n; i++) cin >> a[i];
		cout << solve(a) << '\n';
	}
	return 0;
}

• $s[i]$: 表示 $a[1..i]$ 中 ($1$ 的个数 - $0$ 的个数)
• 对每一个 $s[i]$，要找到最靠左的 $s[j]$ 使得 $s[j] == s[i]$
• 时间复杂度：$O(n^2)$
• 期望得分：$40$ 分

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int T, n;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<int> a(n + 1);
		for (int i = 1; i <= n; i++) cin >> a[i];

		// s[i]: 表示 a[1..i] 中 (1 的个数 - 0 的个数)
		vector<int> s(n + 1, 0);
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			s[i] = s[i - 1] + (a[i] == 1 ? 1 : -1);

			// 查询 s[0] 到 s[i-1] 中是否有 等于 s[i] 的数
			for (int j = 0; j < i; j++) {
				if (s[j] == s[i]) ans = max(ans, i - j);
			}
		}
		cout << ans << '\n';
	}
	return 0;
}