题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
示例 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
题目思考
- 如何在 O(N) 时间内完成?
解决方案
思路
- 根据题目描述, 一个很容易想到的思路是暴力两重遍历, 外层遍历当前起点, 内层向右遍历并维护两者计数
- 但这种方案时间复杂度达到了 O(N^2), 根据题目数据规模, 肯定超时
- 那如何优化呢?
- 这里我们可以利用前缀和的思路:
- 假设子数组[0:i]的字符有 a 个, 数字有 b 个, 而更大的子数组[0:j]有 c 个字符和 d 个数字
- 那么显然当 c-a==d-b 时, 子数组[i+1:j]的字符和数字就相同了, 且都是 c-a
- 而 c-a==d-b, 可以进一步转换成 c-d==a-b, 对应的 c-d 和 a-b 就只与当前前缀子数组有关了, 即它们字符和数字数目的差值 diff
- 对于实际实现, 我们只需要存当前前缀子数组的字符和数字数目的差值 diff
- 然后用一个字典存 {diff: 该 diff 的第一个前缀子数组的终点}
- 最后在遍历过程中根据当前下标 i 的字符串种类, 动态更新 diff 以及字典:
- 如果该 diff 已经存在于字典中: 假设对应的值为 j, 那么根据上述分析, [j+1:i]就是一个字符数字数目相等的子数组, 接下来就是比较它和最终结果的长度了
- 如果该 diff 尚未存在于字典中: 则说明该下标是对应 diff 的首个终点下标, 将其加入字典即可
- 另外注意在初始化字典时需要额外存储{0:-1}, 代表空字符串的情况, 从而可以处理[0:i]本身的字符和数字数目相同的情况
- 下面的代码对必要步骤有详细的解释, 方便大家理解
复杂度
- 时间复杂度 O(N): 只需要遍历数组一遍
- 空间复杂度 O(N): 额外字典, 最多包含 N 个键值对
代码
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
# 前缀差值计数+首个终点下标字典
diff = 0
# s,e存储最终子数组的起点和终点, 初始化e为-1, 代表没有有效解的情况
s, e = 0, -1
# 初始化diff值0的首个终点下标为-1, 用于处理子数组[0:i]的字符和数字的数目恰好相同的情况
diffToFirstEnd = {0: -1}
for i, c in enumerate(array):
if "0" <= c[0] <= "9":
# 数字, 差值加1
diff += 1
else:
# 字符, 差值加1
diff -= 1
if diff not in diffToFirstEnd:
# 前面的前缀数组中不存在当前diff, 则当前下标就是该diff对应的首个终点下标
diffToFirstEnd[diff] = i
else:
# 前面的前缀数组中存在当前diff, 对应的首个终点下标为firstEnd
# 那么[firstEnd+1:i]子数组的字符和数字个数就是相同的
ns = diffToFirstEnd[diff] + 1
if i - ns > e - s or i - ns == e - s and ns < s:
# 如果当前子数组长度更长, 或对应起点更小, 则更新最终结果
s, e = ns, i
# 区间[s,e]即为最长子数组
return array[s : e + 1]
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号