下花园区住房和城乡建设局网站,推广文章的推广渠道,上海网站建设hxwlkj,宁波建设网上银行面试题 17.05. 字母与数字 给定一个放有字母和数字的数组#xff0c;找到最长的子数组#xff0c;且包含的字母和数字的个数相同。 返回该子数组#xff0c;若存在多个最长子数组#xff0c;返回左端点下标值最小的子数组。若不存在这样的数组#xff0c;返回一个空数组。…面试题 17.05. 字母与数字 给定一个放有字母和数字的数组找到最长的子数组且包含的字母和数字的个数相同。 返回该子数组若存在多个最长子数组返回左端点下标值最小的子数组。若不存在这样的数组返回一个空数组。 和昨天的很像呀但是我在数组拷贝的时候 写成了res[i]array[i]然后一直越界找了半天bug真的有被自己蠢到。。。。 思路 将字符串数组转化为前缀和数组为字母的记为1分为数字的记为-1分那么当连续子数组的总分为0时该子数组包含的字母和数字的个数相同。 实现 统计前缀和数组对于每一个右边界此时的前缀和记为sum寻找合法的左边界当左边界的前缀和也为sum时子数组array[left,right]中字母和数字的个数相同记录最长合法子数组的左右边界 class Solution {public String[] findLongestSubarray(String[] array) {int n array.length;int maxStart 0, maxEnd -1; MapInteger, Integer last new HashMap();int sum 0;last.put(0, 0);for (int i 0; i n; i){if (Character.isLetter(array[i].charAt(0))){sum 1;}else{sum - 1; } if (last.containsKey(sum)){int j last.get(sum);if (i 1 - j maxEnd - maxStart){maxEnd i 1;maxStart j;} }else{last.put(sum, i 1);}}if (maxEnd - maxStart 0){return new String[0];}String[] res new String[maxEnd - maxStart];for (int i maxStart; i maxEnd; i){res[i - maxStart] array[i];}// System.arraycopy(array, maxStart, res, 0, maxEnd - maxStart);// return Arrays.copyOfRange(array, maxStart, maxEnd);return res;}
}复杂度 时间复杂度O(n)O(n)O(n)空间复杂度O(n)O(n)O(n)
