Java版LeetCode

Appearance

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

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

输出: []

提示：

  • array.length <= 100000

题解 ​

java
public String[] findLongestSubarray(String[] array) {
    int len = array.length, dv = 0, max = 0, from = 0;
    // 字母数字相差个数 负数为前半 正数为后半
    int[] cache = new int[2 * len];
    Arrays.fill(cache, -2);
    // 特殊处理开始位置 任何数字字母差值为0的是从数组开始位置
    cache[len] = -1;
    for (int i = 0; i < len; i++) {
        if (Character.isDigit(array[i].charAt(0))) {
            dv++;
        } else {
            dv--;
        }
        // 数字字母个数不同 则找到差值相同索引最小位置
        int index = cache[dv + len];
        if (index != -2) {
            // 长度
            int t = i - index;
            if (t > max) {
                max = t;
                from = index + 1;
            }
        } else {
            // 记录差值最小索引位置
            cache[dv + len] = i;
        }
    }

    return Arrays.copyOfRange(array, from, from + max);
}
public String[] findLongestSubarray(String[] array) {
    int len = array.length, dv = 0, max = 0, from = 0;
    // 字母数字相差个数 负数为前半 正数为后半
    int[] cache = new int[2 * len];
    Arrays.fill(cache, -2);
    // 特殊处理开始位置 任何数字字母差值为0的是从数组开始位置
    cache[len] = -1;
    for (int i = 0; i < len; i++) {
        if (Character.isDigit(array[i].charAt(0))) {
            dv++;
        } else {
            dv--;
        }
        // 数字字母个数不同 则找到差值相同索引最小位置
        int index = cache[dv + len];
        if (index != -2) {
            // 长度
            int t = i - index;
            if (t > max) {
                max = t;
                from = index + 1;
            }
        } else {
            // 记录差值最小索引位置
            cache[dv + len] = i;
        }
    }

    return Arrays.copyOfRange(array, from, from + max);
}