每日算法系列【LeetCode 面试题 17.05】字母与数字
题目描述
给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。
返回该子数组，若不存在这样的数组，返回一个空数组。
示例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
题解
回忆之前做过的一道题目：每日算法系列【LeetCode 523】连续的子数组和，是不是有点相似？那道题是要求是否含有总和为 的整数倍的连续子数组。而本题要求的是最长的子数组，满足数字和字母个数相等。
我们可以把字母抽象成 ，数字抽象成
，那么子数组的总和含义就是数字个数与字母个数的差值。假设子数组
是满足字母个数和数字个数相等的，那么这段子数组总和必然是
。如果我们用前缀和来进行优化的话，
，也就是说
和
的值是相等的。
所以我们只需要求一遍前缀和，如果 没有在之前出现过，那就保存一下
最开始出现的下标是
。否则的话就看一下当前子数组长度
和历史最优的长度
谁大，然后决定更不更新。
实际实现中 c++ 还是可以采用 unordered_map 来当作哈希表保存下标。
时间复杂度是 。
代码
c++
class Solution {
public:
vector<string> findLongestSubarray(vector<string>& array) {
int n = array.size();
unordered_map<int, int> mp;
mp[0] = -1;
int cnt = 0, l = 0, r = 0;
for (int i = 0; i < n; ++i) {
cnt += isdigit(array[i][0]) ? 1 : -1;
if (mp.find(cnt) != mp.end()) {
if (r-l < i-mp[cnt]) {
l = mp[cnt] + 1;
r = i + 1;
}
} else {
mp[cnt] = i;
}
}
return vector<string>(array.begin()+l, array.begin()+r);
}
};
python
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
mp = {0: -1}
cnt, l, r = 0, 0, 0
for i, s in enumerate(array):
cnt += 1 if s[:1].isdigit() else -1
if cnt in mp:
if r-l < i-mp[cnt]:
l = mp[cnt] + 1
r = i + 1
else:
mp[cnt] = i
return array[l:r]
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
投递荣耀等公司10个岗位 >
