字母和数字

面试题 17.05. 字母与数字

难度中等34收藏分享切换为英文接收动态反馈

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

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

示例 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

前缀和+哈希表

将数字看成1，字母看成-1,如果前面一个位置的前缀和与当前位置的前缀和相同，那么说明这两个位置中间的前缀和为0，也就是这个字符串的字母的数量和数字的数量相同。只需要计算两个index中间的差值判断是否大于最大值，最终即可得到子数组。

class Solution {
    public String[] findLongestSubarray(String[] array) {
        int len = array.length;
        int cnt = 0, max = 0, start = 0, end = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < len; i++) {
            char c = array[i].charAt(0);
            cnt += Character.isDigit(c) ? -1 : 1;

            if (map.containsKey(cnt)) {
                int lastIndex = map.get(cnt);
                if (i - lastIndex > max) {
                    max = i - lastIndex;
                    start = lastIndex;
                    end = i;
                }
            } else {
                map.put(cnt, i);
            }
        }
        return Arrays.copyOfRange(array, start + 1, end + 1);
    }
}

赏

谢谢你请我吃糖果

微信