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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-longest-subarray-lcci

2.思路

（1）前缀和 & 哈希表
思路参考本题官方题解。

3.代码实现（Java）

//思路1————前缀和 & 哈希表
class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> indices = new HashMap<Integer, Integer>();
        indices.put(0, -1);
        //前置和
        int sum = 0;
        //最长子数组的长度
        int maxLength = 0;
        //最长子数组的起始下标，初始值为 -1
        int startIndex = -1;
        int length = array.length;
        for (int i = 0; i < length; i++) {
            if (Character.isLetter(array[i].charAt(0))) {
            	//将字母看作 1
                sum++;
            } else {
	          	//将数字看作 -1
                sum--;
            }
            if (indices.containsKey(sum)) {
                int firstIndex = indices.get(sum);
                if (i - firstIndex > maxLength) {
                	//更新 maxLength 与 startIndex
                    maxLength = i - firstIndex;
                    startIndex = firstIndex + 1;
                }
            } else {
            	//存储当前前缀和 sum 以及对应的下标 i
                indices.put(sum, i);
            }
        }
        if (maxLength == 0) {
            return new String[0];
        }
        String[] res = new String[maxLength];
        /*
        	System.arraycopy() 中的 5 个参数含义依次如下:
			Object src: 原数组
			int srcPos: 从原数据的起始位置开始
			Object dest: 目标数组
			int destPos: 目标数组的开始起始位置
			int length: 要拷贝的数组的长度
		*/
        System.arraycopy(array, startIndex, res, 0, maxLength);
        return res;
    }
}