【LeetCode每日一题:[面试题 17.05] 字母与数字-前缀和+Hash表】_leecode 前缀和习题

题目描述

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

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

示例 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. 首先我们查看题目给定的数据范围去大致确定一个求解的策略；
2. 然后我们对给定的题目进行题目分析，题目要求我们从一个只有字母和数字组成的数组中去找到最长的子数组，这个最长的子数组中字母和数字的个数是需要相同的；
3. 读完题目大家肯定还是有些疑惑？我们可以对题目做一个简单的转化，你可能就熟悉了，我们可以将最长子数组中字母和数字个数相同的最长长度，转换为最长子数组和为0；
4. 有同学就有疑问了？怎么求最长子数组和为0呢？我们可以在遍历这个字符串数组中把遇到的数字进行加1操作，遇到的字母进行减1的操作，或者反过来都是可以的，该过程通过预处理前缀和求解；
5. 接下来我们在遍历前缀和数组的时候，如果直接通过双重循环求解最终结果的话，肯定是超时，那么该怎么解决呢？我们可以通过Hash表记录位置来进行求解。
6. 此时我们可以通过Hash表来求解，该过程的思路和俩数之和的思路很想，在收集答案的过程中，此时我们需要维护一个前缀和等于0的区间。right-left=0,也就是right=left。
7. 如果当前Hash表不包含当前的值，直接加入当前值作为key，和当前的下标作为value。如果存在当前的key，那么我们就可以尝试更新答案，找到最长的子串，并且记录最左的位置在哪里。
8. 最后，我们找到了left最长子数组的最左下标，max最长子数组的长度，此时我们开辟数组空间，直接求解。返回最终收集到的数据。

实现代码

class Solution {
    public String[] findLongestSubarray(String[] array) {
        int n=array.length;
        int[] arr=new int[n+1];
        for(int i=0;i<n;i++){
            arr[i+1]=arr[i]+(Character.isLetter(array[i].charAt(0))?-1:1);
        }
        HashMap<Integer,Integer> map=new HashMap<>();
        map.put(0,0);
        int max=0,left=-1;
        for(int i=0;i<=n;i++){
            int curSum=arr[i];
            if(map.containsKey(curSum)){
                if(i-map.get(curSum)>max){
                    max=i-map.get(curSum);
                    left=map.get(curSum);
                }
            }else{
                map.put(curSum,i);
            }
        }
        String[] res;
        if(left!=-1){
            res=new String[max];
            int cnt=0;
            for(int i=left;i<left+max;i++){
                res[cnt++]=array[i];
            }
        }else{
            res=new String[]{};
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

运行结果