面试题 17.05. 字母与数字

题目链接

面试题 17.05. 字母与数字 mid

题目描述

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

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

示例 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\le 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)$

C++代码：

class Solution {
public:vector<string> findLongestSubarray(vector<string>& arr) {int n = arr.size();unordered_map<int,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 vector<string> (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:idx+len]