leetcode [17.05] 字母和数字

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

返回该子数组，若不存在这样的数组，返回一个空数组。

示例 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，字符看作-1，统计到当前位置的和，如果两个位置和相同，表示这个区间内数字和字符出现的次数一样，作为一个候选。最后算最大的区间。

from collections import defaultdict
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        count = [0]
        dic = defaultdict(list)
        dic[0].append(0)
        for a in array:
            if a.isdigit():
                count.append(count[-1] + 1)
            else:
                count.append(count[-1] - 1)
            dic[count[-1]].append(len(count) - 1)
        longest = 0
        long_min, long_max = 0, 0
        for k, v in dic.items():
            if v[-1] - v[0] > longest:
                longest = v[-1] - v[0]
                long_min, long_max = v[0], v[-1]
        return array[long_min: long_max]