程序员面试金典-面试题 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"]

输出: []

分析：

利用前缀和，参考了https://leetcode-cn.com/problems/find-longest-subarray-lcci/solution/shu-zi-1-zi-mu-1-by-gfu/的答案。

使用hashmap存储每个前缀和的最左坐标，初始将0，-1存入map中，如果当前前缀和在map中出现，就计算此时的数组左右边界的差值，更新最大的坐标和长度，最否构建新的数组即可。

程序：

class Solution {
    public String[] findLongestSubarray(String[] array) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int l = -1;
        int len = 0;
        int sum = 0;
        map.put(0, -1);
        for(int i = 0; i < array.length; ++i){
            char c = ' ';
            for(char ch:array[i].toCharArray())
                c = ch;
            if(c >= '0' && c <= '9'){
                sum--;
            }else{
                sum++;
            }
            if(!map.containsKey(sum)){
                map.put(sum, i);
            }else{
                if(i - map.get(sum) > len){
                    l = map.get(sum);
                    len = i - l;
                }
            }
        }
        String[] res = new String[len];
        for(int i = 1; i <= len; ++i){
            res[i-1] = array[i+l];
        }
        return res;
    }
}