难度: Medium
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 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运行时间: 82 ms
内存: 33.1 MB
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
prefix_index_dict = {0: -1}
start = -1
max_len = 0
int_str_list = [str(i) for i in range(10)]
prefix_sum = 0
for i in range(len(array)):
if array[i].isdigit():
prefix_sum += 1
else:
prefix_sum -= 1
if prefix_sum not in prefix_index_dict:
prefix_index_dict[prefix_sum] = i
else:
last_index = prefix_index_dict[prefix_sum]
if i - last_index > max_len:
max_len = i - last_index
start = last_index + 1
if max_len == 0:
return []
return array[start: start + max_len]
此题解采用前缀和和哈希表的方法来找到包含相同数量字母和数字的最长子数组。首先，定义一个变量prefix_sum作为前缀和，当遇到数字时增加1，遇到字母时减少1。这样，每个位置的prefix_sum值反映了从数组开始到该位置数字和字母的数量差。使用哈希表prefix_index_dict来存储每个前缀和第一次出现的位置。遍历数组，对于每个元素，如果当前前缀和已经在哈希表中存在，则说明从上一次该前缀和出现的位置到当前位置的子数组中字母和数字的数量相等。通过比较并更新最长长度max_len，记录下最长子数组的开始位置。如果最终max_len为0，说明没有找到符合条件的子数组，返回空数组；否则根据记录的开始位置和长度返回子数组。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
prefix_index_dict = {0: -1} # 存储每个前缀和第一次出现的位置，初始为0的前缀和位置为-1
start = -1 # 最长子数组的起始索引
max_len = 0 # 最长子数组的长度
int_str_list = [str(i) for i in range(10)] # 生成数字字符列表，用于检查元素是否为数字
prefix_sum = 0 # 前缀和初始化
for i in range(len(array)):
if array[i].isdigit():
prefix_sum += 1 # 遇到数字，前缀和加1
else:
prefix_sum -= 1 # 遇到字母，前缀和减1
if prefix_sum not in prefix_index_dict:
prefix_index_dict[prefix_sum] = i # 存储新的前缀和及其位置
else:
last_index = prefix_index_dict[prefix_sum] # 获取相同前缀和的上一个位置
if i - last_index > max_len:
max_len = i - last_index # 更新最长长度
start = last_index + 1 # 更新起始索引
if max_len == 0:
return [] # 如果没有找到有效的子数组，返回空数组
return array[start: start + max_len] # 返回最长的符合条件的子数组
在这个问题中，我们需要找到一个字母和数字数量相等的子数组。为了追踪字母和数字的数量差异，我们使用前缀和的方法。通过将数字视为+1，字母视为-1，前缀和就可以表示从数组开始到当前位置为止数字和字母的数量差。如果在某个位置前缀和为0，这意味着从开始到这个位置的子数组中字母和数字的数量完全相等。因此，通过这种设计，我们可以方便地通过前缀和的变化来追踪和定位数量相等的子数组。
记录前缀和第一次出现的位置的目的是为了在之后遇到相同的前缀和时，能够迅速找到最早出现这个前缀和的位置。如果在数组的某个后续位置我们再次遇到相同的前缀和，这意味着从最初记录的位置到这个后续位置之间的子数组中，字母和数字的增减抵消了，即这部分子数组中字母和数字的数量相等。通过这种方式，我们可以用当前的索引减去哈希表中记录的索引来计算出这个子数组的长度，并持续更新我们找到的最长的满足条件的子数组。
当我们在遍历数组时，每次通过增加1或减少1来更新前缀和，这反映了从数组开始到当前元素为止，数字和字母的总数量差。当我们在哈希表中找到一个已经存在的前缀和时，这意味着从哈希表中记录的位置到当前位置的前缀和增减彼此抵消了。换句话说，这两个位置之间的子数组中，字母和数字的增减数相等，因此它们的数量也必然相等。这就是为什么当我们发现相同的前缀和时可以确定找到了一个数量相等的子数组。