2023-03-11 LeetCode：面试题 17.05. 字

面试题 17.05. 字母与数字

问题描述

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例

输入: ["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"]

输入: ["A","A"]
输出: []

解题思路

这道题可以看作昨天前缀和题型的一种复习，需要进行一定的转换：
如果是字母或数字，当作-1或1。

代码示例（JAVA）

class Solution {
    public String[] findLongestSubarray(String[] array) {
        int length = array.length;
        // 前缀和
        Map<Integer, Integer> map = new HashMap<>();
        int currentSum = 0, start = 0, maxLength = 0;
        for (int i = 0; i < length; i++) {
            // 为保证长度最长，优先使用之前存进去的数据
            if (!map.containsKey(currentSum)) {
                map.put(currentSum, i);
            }
            // 将字符串进行转换，数字为1，字母为-1
            if (Character.isLetter(array[i].charAt(0))) {
                currentSum--;
            } else {
                currentSum++;
            }
            if (currentSum == 0) {
                start = 0;
                maxLength = i + 1;
            } else {
                if (map.containsKey(currentSum)) {
                    int pos = map.get(currentSum);
                    // 比较长度，如果当前的长度更长，更新结果
                    if (i - pos > maxLength) {
                        start = pos;
                        maxLength = i - start + 1;
                    }
                }
            }
        }

        // 找不到
        if (maxLength == 0) {
            return new String[0];
        }
        String[] result = new String[maxLength];
        System.arraycopy(array, start, result, 0, maxLength);
        return result;
    }
}

时间复杂度：O(n)