面试题 17.05. 字母与数字

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例：

输入: ["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"]

分析： 首先前k个数组长度的数字字母个数差值，k∈[0, n], 如果出现差值为0，则表明区间[0, k]数字字母数相同，如果出现不同位差值相同的情况，比如第 k 1 k_1 k1​位和 k 2 k_2 k2​位相同，则说明区间 ( k 1 , k 2 ] (k_1, k_2] (k1​,k2​]的数字字母数相同，创建一个字典，key是差值，value记录区间的起始点，当遇到相同差值时，变可以求出区间长度，保留长度最大的即可

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        max_length = 0
        sub_array = []
        count_array = [0]*len(array)
        count_array[-1] = 0
        count_dict = {}
        count_dict[0] = -1 #数字字母数差值为0，说明起始点在第一位
        for i in range(len(array)):
            if array[i].isdigit():  
                count_array[i] = count_array[i-1] + 1
            else:
                count_array[i] = count_array[i-1] - 1

            if count_array[i] not in count_dict:
                count_dict[count_array[i]] = i
            else:
                left = count_dict[count_array[i]]
                length = i - left
                if length > max_length:
                    max_length = length
                    sub_array = array[left+1:i+1]
        return sub_array