面试题 17.05. 字母与数字

1. 题目描述

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

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

示例 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

标签 数组 哈希表 前缀和

2. 解题

大体思路如下：

• 由于数组中只存在字母和数字两种情况，因此我们可以将字母记为-1，数字记为1来简化问题；

• 题目要求子数组中的字符和数字个数相同，因此我们可以考虑通过求解前缀和来解决这个问题，解分为两种情况：

  • 两个前缀和的值相同，例如：prefix[i]==prefix[j]，说明[0,i]和[0,j]之间多余数字或字符的个数相同，那么如果我们用区间[0,j]减去区间[0,i]之后，在(i,j]之间的数字和字符个数必然相同，因此[(i,j]可能是一组解(注意此处得区间是左开右闭的)；
  • 前缀和为0处，例如：prefix[i]=0，说明 [0,i]之间的数字和字符个数相同，所以[0,j]可能是一组解；

由于题目中需要求得最长的子数组，并且长度相同时以左边最小的子数组作为开头，因此最终答案需要找到前缀和相同的子数组和前缀和为0的子数组最大的那一个即可。