type
status
date
slug
summary
tags
category
icon
password
题目
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 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
思路
- 看到 100000 这个数量就知道不能用 n2 的复杂度了，而且这题没有明显的二分特点，所以只能考虑 n 的时间复杂度，那么只能考虑使用哈希表降低搜索范围了。
- 但是哈希表里应该保存什么呢？因为我们要求的是子数组里数字和字符数量相同，那么在枚举右端点的时候，我们需要快速找到能够让区间满足要求的左端点。这引导我们考虑采用前缀和的方式做处理，只要右端点的“数字出现的次数 - 字符串出现的次数”的差值等于左端点就可以满足要求了。前缀和的计算方式：
- 因为题目要求在区间长度相同时返回最左区间，所以哈希表的记录的是键为“数字出现的次数 - 字符串出现的次数”，值为这个键出现最早的位置。