五是做好纪检监察网站建设,长春网站建设于健,国外服务器网站,贵阳酒店网站建设题目描述
给定一个放有字母和数字的数组#xff0c;找到最长的子数组#xff0c;且包含的字母和数字的个数相同。
返回该子数组#xff0c;若存在多个最长子数组#xff0c;返回左端点下标值最小的子数组。若不存在这样的数组#xff0c;返回一个空数组。
示例 1:
输入…
题目描述
给定一个放有字母和数字的数组找到最长的子数组且包含的字母和数字的个数相同。
返回该子数组若存在多个最长子数组返回左端点下标值最小的子数组。若不存在这样的数组返回一个空数组。
示例 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
求解思路
首先我们查看题目给定的数据范围去大致确定一个求解的策略然后我们对给定的题目进行题目分析题目要求我们从一个只有字母和数字组成的数组中去找到最长的子数组这个最长的子数组中字母和数字的个数是需要相同的读完题目大家肯定还是有些疑惑我们可以对题目做一个简单的转化你可能就熟悉了我们可以将最长子数组中字母和数字个数相同的最长长度转换为最长子数组和为0有同学就有疑问了怎么求最长子数组和为0呢我们可以在遍历这个字符串数组中把遇到的数字进行加1操作遇到的字母进行减1的操作或者反过来都是可以的该过程通过预处理前缀和求解接下来我们在遍历前缀和数组的时候如果直接通过双重循环求解最终结果的话肯定是超时那么该怎么解决呢我们可以通过Hash表记录位置来进行求解。此时我们可以通过Hash表来求解该过程的思路和俩数之和的思路很想在收集答案的过程中此时我们需要维护一个前缀和等于0的区间。right-left0,也就是rightleft。如果当前Hash表不包含当前的值直接加入当前值作为key和当前的下标作为value。如果存在当前的key那么我们就可以尝试更新答案找到最长的子串并且记录最左的位置在哪里。最后我们找到了left最长子数组的最左下标max最长子数组的长度此时我们开辟数组空间直接求解。返回最终收集到的数据。
实现代码
class Solution {public String[] findLongestSubarray(String[] array) {int narray.length;int[] arrnew int[n1];for(int i0;in;i){arr[i1]arr[i](Character.isLetter(array[i].charAt(0))?-1:1);}HashMapInteger,Integer mapnew HashMap();map.put(0,0);int max0,left-1;for(int i0;in;i){int curSumarr[i];if(map.containsKey(curSum)){if(i-map.get(curSum)max){maxi-map.get(curSum);leftmap.get(curSum);}}else{map.put(curSum,i);}}String[] res;if(left!-1){resnew String[max];int cnt0;for(int ileft;ileftmax;i){res[cnt]array[i];}}else{resnew String[]{};}return res;}
}运行结果
