东莞海天网站建设,在线网页代理太太猫,wordpress 标签打不开,企业简介模板ppt免费题目链接 面试题 17.05. 字母与数字 mid 题目描述
给定一个放有字母和数字的数组#xff0c;找到最长的子数组#xff0c;且包含的字母和数字的个数相同。
返回该子数组#xff0c;若存在多个最长子数组#xff0c;返回左端点下标值最小的子数组。若不存在这样的数组找到最长的子数组且包含的字母和数字的个数相同。
返回该子数组若存在多个最长子数组返回左端点下标值最小的子数组。若不存在这样的数组返回一个空数组。
示例 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≤100000array.length \leq 100000array.length≤100000
分析前缀和 哈希表
我们可以将 字母看作是 1数字看作是 -1那么原问题就转换为 求最长的一段和 sum 0的子数组。
我们用一个哈希表 m来记录遍历过的 前缀和 s[i]和它对应的下标 i。
如果当前遍历到了 s[j]并且 m存在 s[j]这个键。由此我们可以得到 i m[s[j]]。那么 (i , j]这一段就是和为 0
的子数组我们就将答案更新即可。
我们用 idx代表最长的那段子数组的起始下标用 len表示最长的那段子数组的长度。
最后返回 array的这一段 [idx , idx len]即可。
时间复杂度 O(n)O(n)O(n)
C代码
class Solution {
public:vectorstring findLongestSubarray(vectorstring arr) {int n arr.size();unordered_mapint,int m{{0,-1}};int idx 0 , len 0;for(int j 0 ,s 0;j n;j){s (arr[j][0] A ? 1 : -1);if(m.count(s)){int i m[s];if(j - i len){len j - i;idx i 1;}}else m[s] j;}return vectorstring (arr.begin() idx,arr.begin() idx len);}
};
Python代码 class Solution:def findLongestSubarray(self, arr: List[str]) - List[str]:m {0:-1}s idx len 0for j,str in enumerate(arr):s 1 if str.isalpha() else -1if s in m:i m[s]if len j - i:idx i 1len j - ielse:m[s] j return arr[idx:idxlen]
