程序员面试金典 - 面试题 17.05. 字母与数字（哈希map+思维转换）

112 阅读 0 评论 74 点赞

我是靠谱客的博主魔幻面包，这篇文章主要介绍程序员面试金典 - 面试题 17.05. 字母与数字（哈希map+思维转换），现在分享给大家，希望可以做个参考。

1. 题目

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
示例 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）
链接：https://leetcode-cn.com/problems/find-longest-subarray-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

将字符设为 -1，数字设为 +1
在sum=0的位置可知 [0,i] 满足字符与数字相等
出现其他和，第一次出现记录其位置 map[sum] = i
后序出现sum，将其位置 i 与 map[sum] 做差求长度，更新最大长度

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        if(array.size() < 2)
            return {};
        unordered_map<int, int> m;
        int start = 0, end = 0, sum = 0;
        for(int i = 0; i < array.size(); ++i)
        {
            if(isdigit(array[i][0]))
                sum++;
            else
                sum--;
            if(sum == 0)//等于0，表示[0,i]满足题意
                start = 0, end = i; 
            else if(!m.count(sum))//其他数字，记录起点
                m[sum] = i; 
            else if(i-m[sum] > end-start+1)//map包含sum，长度更大
            {
                start = m[sum]+1;//更新区间端点
                end = i;
            }
        }
        if(start == end)
            return{};
        return vector<string>(array.begin()+start, array.begin()+end+1);
    }
};