给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 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"] 输出: []
提示：
array.length <= 100000
提示 1
是哪个字母或数字并不重要。你可以把该问题简化为只包含 A 和 B 的数组。然后寻找具有相同数量的 A 和 B 的最长子数组。
提示 2
从蛮力解法开始。
提示 3
如果你从一开始就计算 A 的个数和 B 的个数会怎样(试着构建数组构成的表并保存到目前为止 A 和 B 的数量)?
提示 4
当表中 A 和 B 的个数相等时，整个子数组(从索引 0 开始)的 A 和 B 的个数相等。如何使用该表来查找不以索引 0 开始的、符合条件的子数组?
提示 5
假设在这个表中，索引 i 满足 count(A, 0->i) = 3 和 count(B, 0->i) = 7。这意味着 B 比 A 多 4 个。如果你发现后面的某点 j 具有相同的差值(count(B, 0->j) - count(a, 0->j))，那么这表示子数组中有相同数量的 A 和 B。
解法1：转换 + 前缀和 + 哈希表
一个子数组包含的字母和数字的个数相同，等价于该子数组包含的字母和数字的个数之差为 0。因此可以将原数组做转换，每个字母对应 1，每个数字对应 −1，则转换后的数组中，每个子数组的元素和为该子数组对应的原始子数组的字母和数字的个数之差，如果转换后数组中的一个子数组的元素和为 0，则该子数组对应的原始子数组包含的字母和数字的个数相同。问题等价于在转换后的数组中寻找元素和为 0 的最长子数组。
为了在转换后的数组中寻找元素和为 0 的子数组，可以计算转换后的数组的前缀和，如果两个下标对应的前缀和相等，则这两个下标之间的子数组的元素和为 0。
如果同一个前缀和出现多次，则该前缀和对应的最长子数组的长度为该前缀和的第一次出现的下标与最后一次出现的下标之间的子数组，因此为了在转换后的数组中寻找元素和为 0 的最长子数组，需要记录每个前缀和第一次出现的下标。
使用哈希表记录每个前缀和第一次出现的下标。由于空前缀的前缀和是 0 且对应下标 −1，因此首先将前缀和 0 与下标 −1 存入哈希表。
从左到右遍历数组，遍历过程中维护元素和为 0 的最长子数组的长度 maxLength 与开始下标 startIndex，初始时 maxLength=0，startIndex=−1。当遍历到下标 i 时，如果前缀和是 sum，则执行如下操作。
- 如果哈希表中已经存在前缀和 sum，则从哈希表中得到前缀和 sum 第一次出现的下标 firstIndex，以下标 i 结尾的元素和为 0 的最长子数组的长度是 i−firstIndex，该最长子数组的下标范围是 [firstIndex+1,i]。如果 i−firstIndex>maxLength，则将 maxLength 更新为 i−firstIndex，将 startIndex 更新为 firstIndex+1；如果 i−firstIndex≤maxLength，则不更新 maxLength 与 startIndex。
- 如果哈希表中不存在前缀和 sum，则下标 i 为前缀和 sum 第一次出现的下标，将前缀和 sum 与下标 i 存入哈希表。
遍历结束之后，根据 maxLength 与 startIndex 的值返回结果。
- 如果 maxLength>0，则原数组中存在字母和数字的个数相同的子数组，根据 maxLength 与 startIndex 得到原数组中包含的字母和数字的个数相同的最长子数组，返回该最长子数组。
- 如果 maxLength=0，则原数组中不存在字母和数字的个数相同的子数组，返回空数组。
从左到右遍历数组的过程中，只有当遇到的子数组长度大于已有的最大长度时才会更新最大子数组的长度与开始下标，因此每次更新最大子数组的长度与开始下标之后，不存在长度等于已有的最大长度且开始下标更小的子数组。如果有多个最长子数组，则 startIndex 为这些最长子数组中的最小的左端点下标值。
实现方面，不需要创建并计算转换后的数组，只需要将原数组中的字母和数字分别对应 1 和 −1，在遍历过程中计算前缀和即可。
Java版：
在Java中，System类包包含一个名为arraycopy()的方法来复制数组。
arraycopy(Object src, int srcPos,Object dest, int destPos, int length)
这里，
-
src -您要复制的源数组
-
srcPos -源数组中的起始位置（索引）
-
dest -目标数组，将从源中复制元素
-
destPos -目标数组中的起始位置（索引）
-
length -要复制的元素数
class Solution {
public String[] findLongestSubarray(String[] array) {
int maxLength = 0;
int start = -1;
int presum = 0;
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < array.length; i++) {
if (Character.isLetter(array[i].charAt(0))) {
presum++;
} else {
presum--;
}
if (map.containsKey(presum)) {
if (i - map.get(presum) > maxLength) {
maxLength = i - map.get(presum);
start = map.get(presum) + 1;
}
} else {
map.put(presum, i);
}
}
if (maxLength == 0) {
return new String[0];
}
String[] ans = new String[maxLength];
System.arraycopy(array, start, ans, 0, maxLength);
return ans;
}
}Python3版：
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
maxLength = 0
start = -1
presum = 0
dic = dict()
dic[0] = -1
for i in range(len(array)):
if array[i].isdigit():
presum += 1
else:
presum -= 1
if presum in dic:
if i - dic[presum] > maxLength:
maxLength = i - dic[presum]
start = dic[presum] + 1
else:
dic[presum] = i
if maxLength == 0:
return []
return array[start: start + maxLength]复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组一次计算符合要求的最长子数组的长度与开始下标，对于数组中的每个元素的操作时间都是 O(1)，因此遍历时间是 O(n)，生成结果数组需要 O(n) 的时间。
- 空间复杂度：O(n)，其中 n 是数组的长度。哈希表需要 O(n) 的空间。