gold-17-5

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

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

示例 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 submit region begin(Prohibit modification and deletion)
class Solution {
    public String[] findLongestSubarray(String[] array) {
        int[] numCnt = new int[array.length + 1];
        numCnt[0] = 0;
        int maxLen = -1;
        int maxFrom = -1;
        int maxTo = -1;

        for (int i = 0; i < array.length; i++) {
            char ch = array[i].charAt(0);
            if (ch >= '0' && ch <= '9') {
                numCnt[i + 1] = numCnt[i] + 1;
            } else {
                numCnt[i + 1] = numCnt[i];
            }
        }

        for (int i = 2; i <= array.length; i++) {
            for (int j = i % 2; j < i; j+=2) {
                if (i - j <= maxLen) {
                    break;
                }
                if (numCnt[i] - numCnt[j] == (i - j) / 2) {
                    int len = i - j;
                    if (len > maxLen) {
                        maxLen = len;
                        maxFrom = j;
                        maxTo = i - 1;
                    }
                }
            }
        }

        if (maxLen == -1) {
            return new String[0];
        } else {
            String[] result = new String[maxTo - maxFrom + 1];

            for (int i = maxFrom; i <= maxTo; i++) {
                result[i - maxFrom] = array[i];
            }

            return result;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)