LeetCode每日一题（2023/3/11）

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

解答：哈希表+前缀和

class Solution {
    public String[] findLongestSubarray(String[] array) {
        // 创建一个 Map 用于存储数组的前缀和作为键，下标作为值
        Map<Integer,Integer> map=new HashMap<>();
        // 将长度最长子数组的起始和结束下标初始化为0
        int end=0,start=0;
        // 将0作为前缀和放入 Map 中，并将其下标设为-1，以处理最长子数组起始下标为0的情况
        map.put(0,-1);
        // 定义一个变量来存储当前的前缀和
        int presum=0;
        // 遍历字符串数组
        for(int i=0;i<array.length;i++){
            // 判断当前字符串是否是数字，是则前缀和加1，否则前缀和减1
            presum+=Character.isDigit(array[i].charAt(0))?1:-1;
            // 如果当前前缀和在 Map 中已经存在，则说明前面有一段子数组的和与当前子数组相等，计算它们的距离
            if(map.containsKey(presum)){
                int l=map.get(presum);
                if(i-l>end-start){
                    end=i;
                    start=l;
                }
            }
            // 如果当前前缀和不存在于 Map 中，则将其存入 Map 中
            else{
                map.put(presum,i);
            }
        }
        // 返回长度最长的子数组
        return Arrays.copyOfRange(array,start+1,end+1);
    }
}