难度：
m
i
d
d
l
e
\color{orange}{middle}
middle
题目描述
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 1:
输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]
输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
示例 2:
输入: ["A","A"]
输出: []
提示：
-
a
r
r
a
y
.
l
e
n
g
t
h
<
=
100000
array.length <= 100000
array.length<=100000
算法
(前缀和 + 哈希表)
题目要求找到最长的子数组，且包含的字符和数字的个数相同。我们可以将字符看作 1，数字看作 −1，那么问题就转化为：求最长的子数组，使得该子数组的和为 0。
我们可以运用前缀和的思想，用哈希表 hash 记录每个前缀和第一次出现的位置，用变量 mx 和 k 分别记录最长的满足条件的子数组的长度和左端点位置。
接下来遍历数组，计算当前位置 i 的前缀和 s：
-
如果当前位置的前缀和
s在哈希表hash中存在，我们记第一次出现s的位置为j，那么区间[j+1,..,i]的子数组和就为0。如果此前的最长子数组的长度小于当前子数组的长度，即mx<i−j，我们就更新mx=i−j和k=j+1。 -
否则，我们将当前位置的前缀和
s作为键，当前位置 i 作为值，存入哈希表hash中。
遍历结束后，返回左端点为 k，且长度为 mx 的子数组即可。
复杂度分析
-
时间复杂度：
O
(
n
)
O(n)
O(n)
-
空间复杂度 :
O
(
n
)
O(n)
O(n)
C++ 代码
class Solution {
public:
vector<string> findLongestSubarray(vector<string>& array) {
//这里是一个初始化操作，把第一次出现0的点初始化为-1，这样当j为0时i-j的长度是一个正确的值
unordered_map<int, int> mp{{0, -1}};
// s表示前缀和，mx表示最长子数组的长度，k表示最长子数组的左端点
int s = 0, mx = 0, k = 0;
for (int i = 0; i < array.size(); i++) {
// 标定是否为字母，是则为1，不是则为-1
s += array[i][0] >= 'A' ? 1 : -1;
if (mp.find(s) != mp.end()) {
// 判断哈希表中是否存在相同的s
// 如果存在，则接收它的左端点
int j = mp[s];
if (i - j > mx) {
// 判断数组长度i-j是否大于mx
// 如果是，则更新数组长度
mx = i - j;
// 同时更新左端点
// vector复制的范围是左闭右开，设左边界为j+1这样才能取到正确的子数组
k = j + 1;
}
} else {
// 如果不存在相同的s，则将它加入哈希表中
mp.emplace(s, i);
}
}
// 最后，我们得到了最长子数组的左端点和长度，因此可以根据这两个值将最长子数组拷贝出来
return vector<string>(array.begin() + k, array.begin() + k + mx);
}
};