Leetcode-面试题 17.05. 字母与数字

72 阅读 0 评论 48 点赞

我是靠谱客的博主忧伤高跟鞋，最近开发中收集的这篇文章主要介绍Leetcode-面试题 17.05. 字母与数字，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

链接

面试题 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

思路

这题比较巧妙，我们不需要关心具体的数字是0、1、2还是A、B、C，一共分成两类，一类数字、一类字母即可，因此，可以用-1表示任意字母，用1表示任意数字，问题就转换成了找累加和为0的两个区间。

而这类问题我们可以用前缀和来处理，如[-1，1,1，-1,1，-1，-1]其前缀和就是[-1,0,1,0,1,0,-1],而两个前缀和相减为0，这中间的元素和便为0，也就是字母和数字数量相等。

对于我们得到的前缀和数组，我们可以用一个哈希表来处理，每当遇到一个新的前缀和，将其和其下标存入哈希表（也就是只保存该前缀和的第一个下标），而如果遇到的前缀和已经在哈希表中出现过，则用当前的下标减去哈希表中的下标（也就是相同前缀和的第一个下标），然后动态维护最大值和对应的下标i，最后可以得到区间的位置，通过这个位置还原原始字符串数组即可。

C++ Code

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        //前缀和+哈希表
        //字母为-1 数字为1 求和为0的最长区间
        int n=array.size();
        vector<int> sum(n+1,0); //计算前缀和
        int tempsum=0; //临时存放当前前缀和
        for(int i=0;i<n; i++ )
        {
            if('0'<=array[i][0] && array[i][0]<='9')  tempsum+=1;
            else tempsum-=1;
            sum[i+1]=tempsum;
        }
        unordered_map<int,int> map;//记录前缀和以及该前缀和第一次出现的左下标
        int Maxlen=0; //子数组最长长度
        int index=0; //子数组最长时的左下边
        for(int i=0;i<n+1;i++)
        {
            if(map.find(sum[i])!=map.end()) //哈希表中以及存在该前缀和
            {
                if(i-map[sum[i]]>Maxlen)
                {
                    Maxlen=i-map[sum[i]];
                    index=map[sum[i]];
                }
            }
            else map[sum[i]]=i;
        }

        vector<string> result(array.begin()+index,array.begin()+index+Maxlen);
        return result;

    }
};