LeetCode-面试题 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
https://leetcode.cn/problems/find-longest-subarray-lcci/description/

解题思路一：前缀和。数字为-1，字母为1。我们需要找到的子数组是前缀和之差为0的，例如s[right]-s[left]=0，那么s[right]=s[left]，变为找前缀和相同的了。我们用一个字典记录前缀和的最早出现下标。

array.length 非常大，常规暴力算法难以不超时。

注意python里面不是if else 而是if elif

class Solution:def findLongestSubarray(self, array: List[str]) -> List[str]:s=list(accumulate((-1 if v[0].isdigit() else 1 for v in array),initial=0))left=right=0#前缀和一般是左闭右开[left,right)first={}#记录前缀和最早出现的下标for i,v in enumerate(s):j=first.get(v,-1)#v是s[i]出现的最早下标，若无则为-1if j<0:#首次遇到s[i]first[v]=ielif i-j>right-left:    #遇到更长的子数组left,right=j,ireturn array[left:right]

时间复杂度：O(n)
空间复杂度：O(n)

解题思路二：用一个整数替换前缀和列表，在遍历array过程中计算前缀和。其值在[-n,n]之间故数组长设为2n+1。具体看注释。

class Solution:def findLongestSubarray(self, array: List[str]) -> List[str]:left=right=0#前缀和一般是左闭右开[left,right)s=n=len(array)#s初始化为n防止出现负数下标first=[-1]*(2*n+1)#记录前缀和最早出现的下标，初始化为-1长为2n+1的数组first[s]=0#s[0]=0for i,v in enumerate(array,1):#表示i从1开始计数s+=-1 if v[0].isdigit() else 1j=first[s] #first[s]是s[i]出现的最早下标，若无则为-1if j<0:#首次遇到s[i]first[s]=ielif i-j>right-left:    #遇到更长的子数组left,right=j,ireturn array[left:right]

时间复杂度：O(n)
空间复杂度：O(n)

解题思路三：0