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]出现的最早下标，若无则为-1
            if j<0:#首次遇到s[i]
                first[v]=i
            elif i-j>right-left:    #遇到更长的子数组
                left,right=j,i
        return array[left:right]
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：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]=0
        for i,v in enumerate(array,1):#表示i从1开始计数
            s+=-1 if v[0].isdigit() else 1
            j=first[s] #first[s]是s[i]出现的最早下标，若无则为-1
            if j<0:#首次遇到s[i]
                first[s]=i
            elif i-j>right-left:    #遇到更长的子数组
                left,right=j,i
        return array[left:right]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

解题思路三：0

1