面试题 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 <= 10000

记录出错==================================================================’

for i in array:

           if '0'<=i<='9':

               nums.append(1)

           else:

               nums.append(-1)

我就是这样判断是不是数字的，这个bug改了30多分钟，真离谱（这样只能看到1-9的数字，一旦超过9就会出错--）

--------------------------------------------------------------------------------------------------------------------------------- 思路：

将数字变成1，字母变成-1，题目就变成了，给你一个nums=[1,-1,1,1,1,1,-1,-1.....],然后让你求最长等于0的子数组（子数组一定是连续的），这个时候就可以使用前缀和

根据前缀和公式只要presum出现了两次相同,例如 pre[i]==pre[j],则说明nums[i+1]到nums[j]的和为0，这一点可以很直观的看出来，不清楚的可以自己在草稿纸上面画一画

代码如下

class Solution(object):
    def findLongestSubarray(self, array):
        nums=[]
        for i in array:
            if 'A'<=i<='z':
                nums.append(1)
            else:
                nums.append(-1)
        count=0
        presum=0
        dict={0:-1}
        right=0
        left=0
        for i in range(len(nums)):
            presum+=nums[i]
            if presum in dict:
                if i-dict[presum]>count:
                    count=i-dict[presum]
                    right=i
                    left=dict[presum]+1
            else:
                dict[presum]=i
        if count==0:
            return []
        return (array[left:right+1])#左闭右开所以要right+1

具体的实现步骤如下：

1. 遍历输入的数组 array，将每个元素转换为数字字符时，标记为 1，否则标记为 -1，将这些标记存储在列表 nums 中。

2. 初始化变量 ans 为 0，表示最长子数组的长度；presum 表示当前的前缀和；pre 是一个字典，用于存储前缀和及其对应的索引；right 和 left 分别表示最长子数组的右边界和左边界。

3. 遍历 nums 列表，计算当前的前缀和 presum。如果 presum 已经在字典 pre 中出现过，则计算当前索引与之前出现的索引的差值，即当前子数组的长度。如果当前子数组长度大于 ans，则更新 ans、right 和 left。

4. 如果 ans 仍然为 0，则表示没有找到满足条件的子数组，直接返回空列表；否则，返回数组 array 中从 left 到 right 的子数组。

总体来说，这段代码的作用是找到数组中包含相同数量数字字符和非数字字符的最长子数组，并返回该子数组。