python3 解法, 执行用时: 136 ms, 内存消耗: 31.5 MB, 提交时间: 2022-12-02 11:03:46

'''
使用一个字典, 数字与字符数目的差值diff作为key, value是前i个数的差值为key的起始下标
只需要存1个下标, 遇到新的下标的时候直接判断是否要更新s和e即可
注意需要额外处理diff=0的情况
注意结果是[s+1:e]
注意输入存在多位数字的情况..
'''
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        diffToStartIndex = {}
        diff = 0
        s, e = 0, -1
        for i, c in enumerate(array):
            if '0' <= c[0] <= '9':
                diff += 1
            else:
                diff -= 1
            if diff == 0 and i > e - s:
                s, e = -1, i
            if diff not in diffToStartIndex:
                diffToStartIndex[diff] = i
            elif i - diffToStartIndex[diff] > e - s:
                s, e = diffToStartIndex[diff], i
        return array[s + 1:e + 1]

java 解法, 执行用时: 11 ms, 内存消耗: 56 MB, 提交时间: 2022-12-02 11:02:30

class Solution {
    public String[] findLongestSubarray(String[] array) {
        int len = array.length;
        int[] memo = new int[(len << 1) + 1];
        Arrays.fill(memo, -2);
        memo[len] = -1;
        int res = 0, count = 0, begin = 0, end = 0;
        for (int i = 0; i < len; ++i) {
            boolean is_num = true;
            for (char c : array[i].toCharArray())
                if (c < '0' || c > '9') {
                    is_num = false;
                    break;
                }
            count += is_num ? -1 : 1;
            //未曾见过该前缀和(即memo数组中没有记录)
            if (memo[count + len] <= -2) 
                memo[count + len] = i;  //记录该前缀和的下标
            //曾见过该前缀和(即memo数组中已有记录)
            else if (i - memo[count + len] > res) {
                begin = memo[count + len] + 1;
                end = i + 1;
                res = i - memo[count + len];
            }
        }
        return Arrays.copyOfRange(array, begin, end);
    }
}

python3 解法, 执行用时: 132 ms, 内存消耗: 31.9 MB, 提交时间: 2022-12-02 11:00:39

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        dic = {}
        dic[0] = -1 #key: 累加和, value: 当前位置
        _sum = 0
        resL = 0
        resR = 0
        longest = 0
        for i in range(len(array)):
            if array[i].isdigit():
                _sum += 1
            else:
                _sum -= 1      #累加和变化
            target = _sum - 0  #累加和减目标，准备寻找最早出现target的值，当前坐标-最早坐标= 最长值
            if target not in dic:
                dic[target] = i  #初次变化存入字典内
            else:
                right = i
                left = dic[target]
                if right - left > longest:
                    longest = right - left
                    resL = left + 1
                    resR = right +1
        if longest:
            return array[resL : resR]
        else:
            return []

python3 解法, 执行用时: 168 ms, 内存消耗: 33.3 MB, 提交时间: 2022-12-02 10:58:04

'''
数字看成-1，字母看成1，再计算前缀和。

使用int[]数组memo存储 该前缀和 第1次出现时 的下标
'''
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        array_len = len(array)
        memo = [-2 for i in range((array_len << 1) + 1)]
        memo[array_len] = -1
        begin, end = 0, 0
        res, count = 0, 0
        for i in range(array_len):
            is_num = True
            for ch in array[i]:
                if ch.isalpha():
                    is_num = False
                    break
            count += -1 if is_num else 1
            if memo[count + array_len] <= -2:
                memo[count + array_len] = i
            elif i - memo[count + array_len] > res:
                begin, end = memo[count + array_len] + 1, i + 1
                res = i - memo[count + array_len]
        return array[begin:end]