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

输出: []

提示：

• array.length <= 100000

Solutions

class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,0);
        int count=0,start=0,end=0,n=array.length;
        for(int i=0;i<n;i++){
            if(Character.isDigit(array[i].charAt(0))){count++;}
            else{count--;}
            if(map.containsKey(count)){
                int a=map.get(count);
                if(i+1-a>end-start){
                    start=a;
                    end=i+1;
                }
            }
            else{map.put(count,i+1);}
        }
        return Arrays.copyOfRange(array,start,end);
    }
}

Ideas

• 转换 + 前缀和

  一个子数组包含的字母和数字的个数相同，等价于该子数组包含的字母和数字的个数之差为 0。因此可以将原数组做转换，每个字母对应 1，每个数字对应 −1，则转换后的数组中，每个子数组的元素和为该子数组对应的原始子数组的字母和数字的个数之差，如果转换后数组中的一个子数组的元素和为 0，则该子数组对应的原始子数组包含的字母和数字的个数相同。问题等价于在转换后的数组中寻找元素和为 0 的最长子数组。

  为了在转换后的数组中寻找元素和为 0 的子数组，可以计算转换后的数组的前缀和，如果两个下标对应的前缀和相等，则这两个下标之间的子数组的元素和为 0。

  如果同一个前缀和出现多次，则该前缀和对应的最长子数组的长度为该前缀和的第一次出现的下标与最后一次出现的下标之间的子数组，因此为了在转换后的数组中寻找元素和为 0 的最长子数组，需要记录每个前缀和第一次出现的下标。

  使用哈希表记录每个前缀和第一次出现的下标。由于空前缀的前缀和是 0 且对应下标 −1，因此首先将前缀和 0 与下标 −1 存入哈希表。从左到右遍历数组，遍历过程中维护元素和为 0 的最长子数组的长度 maxLength 与开始下标 startIndex，初始时 maxLength=0，startIndex=−1。当遍历到下标 i 时，如果前缀和是 sum，则执行如下操作。

  • 如果哈希表中已经存在前缀和 sum，则从哈希表中得到前缀和 sum 第一次出现的下标 firstIndex，以下标 i 结尾的元素和为 0 的最长子数组的长度是 i−firstIndex，该最长子数组的下标范围是 [firstIndex+1,i]。如果 i−firstIndex>maxLength，则将 maxLength 更新为 i−firstIndex，将 startIndex 更新为 firstIndex+1；如果 i−firstIndex≤maxLength，则不更新 maxLength 与 startIndex。

  • 如果哈希表中不存在前缀和 sum，则下标 i 为前缀和 sum 第一次出现的下标，将前缀和 sum 与下标 i 存入哈希表。

  遍历结束之后，根据 maxLength 与 startIndex 的值返回结果。

  • 如果 maxLength>0 则原数组中存在字母和数字的个数相同的子数组，根据 maxLength 与 startIndex 得到原数组中包含的字母和数字的个数相同的最长子数组，返回该最长子数组。

  • 如果 maxLength=0，则原数组中不存在字母和数字的个数相同的子数组，返回空数组。

  从左到右遍历数组的过程中，只有当遇到的子数组长度大于已有的最大长度时才会更新最大子数组的长度与开始下标，因此每次更新最大子数组的长度与开始下标之后，不存在长度等于已有的最大长度且开始下标更小的子数组。如果有多个最长子数组，则 startIndex 为这些最长子数组中的最小的左端点下标值。

  实现方面，不需要创建并计算转换后的数组，只需要将原数组中的字母和数字分别对应 1 和 −1，在遍历过程中计算前缀和即可。