面试金典--面试题 16.18. 模式匹配（前缀和+哈希表）

本文主要是介绍面试金典--面试题 16.18. 模式匹配（前缀和+哈希表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

题目描述
思路分析
完整代码

题目描述

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 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”]
输出: []

思路分析

将字母看成‘1’，数字看成‘-1’。

比如： [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]

转化为[1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1]

紧接着计算前缀和数组：[1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6]。

将前缀和前面添加一个0，变成[0,1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6]。

为啥要加0？毕竟是前缀和嘛，前缀和下标为1的时候表示array数组前面1个数值的和，区间为[0,1) 左闭右开，刚好符合代码编写习惯。

在前缀和数组中可以发现一个点，前缀和数组里相同的数字代表–在这两个相同数字区间内的数出现字母和数字的次数是相同的。

比如看这2个1：[0,1, 0,1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6]

说明这2个1的下标所构成的区间内的数字和为0，也就是说，无论你怎么折腾，开始为1代表有1个字母，中间折腾了无数次，最后结果也是1代表有1个字母，说明你中间有相同个数的字母和数字使得开始有1个字母，最后也是剩下1个字母。

这时候就找相同数字间隔最远的哪一个子数组就行了。

直接拿哈希表来做。

哈希表key为数字，value为该数字的下标。
哈希表中只记录数字第一次出现的数值。
若其非第一次出现，则计算当前下标和数字第一次出现时的下标的差值，找到最大的哪一个差值即可。

完整代码

class Solution:def findLongestSubarray(self, array: List[str]) -> List[str]:temp = []# 转为数字为-1，字母为1for i in range(len(array)):try:s = int(array[i])temp.append(-1)except:temp.append(1)start = 0ans = [0] # 计算前缀和for i in range(len(temp)):start+=temp[i]ans.append(start)res = []max_length = 0hs = {}#  哈希表找最长子串for i in range(len(ans)):if ans[i] not in hs:hs[ans[i]] = ielse:if i-hs[ans[i]]>max_length:res = array[hs[ans[i]]:i]max_length = i-hs[ans[i]]return res```