面试题 17.05. 字母与数字

面试题 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”]

示例 2:

输入: [“A”,”A”]

输出: []

提示：

array.length <= 100000

思路

1. 看到 100000 这个数量就知道不能用 n2 的复杂度了，而且这题没有明显的二分特点，所以只能考虑 n 的时间复杂度，那么只能考虑使用哈希表降低搜索范围了。
2. 但是哈希表里应该保存什么呢？因为我们要求的是子数组里数字和字符数量相同，那么在枚举右端点的时候，我们需要快速找到能够让区间满足要求的左端点。这引导我们考虑采用前缀和的方式做处理，只要右端点的“数字出现的次数 - 字符串出现的次数”的差值等于左端点就可以满足要求了。
   前缀和的计算方式：

   key += array[i].charAt(0) >= '0' && array[i].charAt(0) <= '9' ? 1 : -1;

3. 因为题目要求在区间长度相同时返回最左区间，所以哈希表的记录的是键为“数字出现的次数 - 字符串出现的次数”，值为这个键出现最早的位置。

代码

class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        int key = 0;
        int left = 0, len = 0;
        map.put(0, -1);
        for(int i=0;i<array.length;i++) {
            key += array[i].charAt(0) >= '0' && array[i].charAt(0) <= '9' ? 1 : -1;
            if(map.containsKey(key)) {
                int pos = map.get(key);
                if( (len < i - pos) || ((len == i - pos) && pos < left) ){
                    len = i - pos;
                    left = pos + 1;
                } 
            }else{
                map.put(key, i);
            }
        }

        return Arrays.copyOfRange(array, left, left + len);
    }
}