【每日一题Day143】面试题 17.05. 字母与数字 | 前缀和+哈希表

class Solution {
    public String[] findLongestSubarray(String[] array) {
        int n = array.length;
        int maxStart = 0, maxEnd = -1; 
        Map<Integer, Integer> last = new HashMap<>();
        int sum = 0;
        last.put(0, 0);
        for (int i = 0; i < n; i++){
            if (Character.isLetter(array[i].charAt(0))){
                sum += 1;
            }else{
                sum -= 1; 
            }        
            if (last.containsKey(sum)){
                int j = last.get(sum);
                if (i + 1 - j > maxEnd - maxStart){
                    maxEnd = i + 1;
                    maxStart = j;
                }                
            }else{
                last.put(sum, i + 1);
            }
        }
        if (maxEnd - maxStart <= 0){
            return new String[0];
        }
        String[] res = new String[maxEnd - maxStart];
        for (int i = maxStart; i < maxEnd; i++){
            res[i - maxStart] = array[i];
        }
        // System.arraycopy(array, maxStart, res, 0, maxEnd - maxStart);
        // return Arrays.copyOfRange(array, maxStart, maxEnd);
        return res;
    }
}