面试题 17.05. 字母与数字

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

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

示例 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

Python 解答：
1.暴力超时

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        a = [[0 for i in range(2)] for j in range(len(array)+1)]
        a[0][0], a[0][1] = 0, 0
        for i in range(1, len(array)+1):
            if array[i-1].isalpha():
                a[i][0] += a[i-1][0]+1
                a[i][1] += a[i-1][1]
            else:
                a[i][0] += a[i-1][0]
                a[i][1] += a[i-1][1]+1
        left, right = 0, 0
        for i in range(0, len(array)+1):
            for j in range(len(array), i, -1):
                if j-i > right-left:
                    if a[j][0]-a[i][0] == a[j][1]-a[i][1]:
                        right, left = j, i
                        break
                else:
                    break
        if right == 0:
            return []
        else:
            return array[left:right]

2.哈希

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        a = [j for j in range(len(array)+1)]
        a[0] = 0
        for i in range(len(array)):
            if array[i].isalpha():
                a[i+1] = a[i]+1
            else:
                a[i+1] = a[i]-1
        adic = {}
        left, right = 0, 0
        for i in range(len(a)):
            if a[i] not in adic.keys():
                adic[a[i]] = i 
            else:
                if i-adic[a[i]] > right-left:
                    left = adic[a[i]]
                    right = i
        return array[left:right]