题目描述

Problem: 面试题 17.05. 字母与数字

文章目录

• 题目描述
• 思路
• 解题方法
• 复杂度
• Code

思路

因为要找到字母和数字个数都相同的情况下，最长数组长度。那么其实就并不需要考虑具体的内容，而只需要关注字符串中的类别即可。只将字符串中看作由字母和数字两个类别组成的结构。

为了便于计算相同个数，将数字作为1，字母作为-1，将字符串中的内容进行转化。对于转化的数组，只要子数组中的元素之和为0，就能保证原字符中数字和字母的个数相同。

为了计算子数组的元素之和，便可以用前缀和的方式进行实现。前缀和常用于解决计算某段区间长度之和的问题。s[i]表示数组中0 ~ i-1之和，如果想要求i - 1 ~ j之间的区间元素之和，就让s[j + 1] - s[i]即可。而我们的目标是找到子数组元素之和为0的区间长度，而满足这一条件的便是从0 ~ n-1之中前缀和相同的
那段区间。当s[i] = s[j]的时候，此时二者之间的区间元素之和一定为0。 因此，找到i与j最大差值的情况即可。

解题方法

遍历各个字符串中构成的前缀和，使用一个哈希表存储第一次遇到的某一值的前缀和，当下次再遍历到相同前缀和时，就计算二者之间的长度之差，找到所有情况中的最大值。

复杂度

• 时间复杂度:

添加时间复杂度, 示例： O(n)O(n)O(n)

• 空间复杂度:

添加空间复杂度, 示例： O(n)O(n)O(n)

Code

class Solution {
public:vector findLongestSubarray(vector& array) {// 构建哈希表存储第一次遇到的前缀和，key：前缀和，value：下标unordered_map record;record[0] = -1;                 // 0表示没有，为了便于后续计算，按下标为-1// startIndex和哈希表中的0表示一致int sum = 0, maxLength = 0, startIndex = -1, n = array.size();for(int i = 0; i < n; i++) {    // 找到数字就前缀和加一，找到字母就前缀和减一if(array[i][0] - '0' >= 0 && array[i][0] - '0' <= 9) {sum++;} else {sum--;}// 如果前缀和已存在，则更新最长长度；如果前缀和不存在，则在哈希表中记录if(record.count(sum)) {int firstIndex = record[sum];           // 获取第一个遇到这一前缀和的下标（前缀和的下标m对应array[0 .. m-1]）if(i - firstIndex > maxLength) {        // 更新最长长度maxLength = i - firstIndex;         startIndex = firstIndex + 1;        }} else {record[sum] = i;}}// 长度为0，没有找到可以让数组和字母相等的子数组，返回空if(maxLength == 0)              return {};// 返回最长长度子数组return vector(array.begin() + startIndex, array.begin() + startIndex + maxLength);}
};

参考文章：字母与数字