字母与数字.md

面试题 17.05. 字母与数字

https://leetcode-cn.com/problems/find-longest-subarray-lcci/

题目描述

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-longest-subarray-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

将数字和字母分别转换成1和-1
计算前缀和
如果前缀和==0
那么就计算区间长度
如果前缀和出现相同的数字
计算区间长度
返回最长的区间长度的内容

python代码

执行用时： 200 ms , 在所有 Python3 提交中击败了 49.01% 的用户 内存消耗： 31.3 MB , 在所有 Python3 提交中击败了 87.42% 的用户

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        length = array.__len__()
        prefix_sum = [0] * length  # 记录前缀和
        left, right = 0, 0  # 记录返回的数组下标
        sub_dict = {}  # 记录出现过的非0前缀和 首次出现的下标
        # 字母标记为1，数字标记为-1
        for i in range(length):
            prefix_sum[i] = 1 if 'A' <= array[i] <= 'z' else -1
        # 记录前缀和
        for i in range(1, length):
            prefix_sum[i] += prefix_sum[i-1]

        for index, _sum in enumerate(prefix_sum):
            # 前缀和为0的，说明下标0 到 index的字母数字出现次数相等，下标包含0和index
            if _sum == 0:
                if right - left < index:
                    left = 0
                    right = index + 1
            else:
                # 前缀和出现过，计算等钱index和首次出现的下标差值，用差值和当前记录的最长字符串长度再做比较，如果大于
                # 当前记录的范围长度，则进行记录
                if _sum in sub_dict:
                    if right - left < index - sub_dict[_sum]:
                        left = sub_dict[_sum] + 1
                        right = index + 1
                else:
                    # 前缀和未出现过，则记录首次出现的下标
                    sub_dict[_sum] = index

        return array[left: right]