字母与数字

Given an array filled with letters and numbers, find the longest subarray with an equal number of letters and numbers.

Return the subarray. If there are more than one answer, return the one which has the smallest index of its left endpoint. If there is no answer, return an empty arrary.

Example 1:

Input: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

Output: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]

Example 2:

Input: ["A","A"]

Output: []

Note:

• array.length <= 100000

此题解采用前缀和和哈希表的方法来找到包含相同数量字母和数字的最长子数组。首先，定义一个变量prefix_sum作为前缀和，当遇到数字时增加1，遇到字母时减少1。这样，每个位置的prefix_sum值反映了从数组开始到该位置数字和字母的数量差。使用哈希表prefix_index_dict来存储每个前缀和第一次出现的位置。遍历数组，对于每个元素，如果当前前缀和已经在哈希表中存在，则说明从上一次该前缀和出现的位置到当前位置的子数组中字母和数字的数量相等。通过比较并更新最长长度max_len，记录下最长子数组的开始位置。如果最终max_len为0，说明没有找到符合条件的子数组，返回空数组；否则根据记录的开始位置和长度返回子数组。

O(n)

O(n)