面试题 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; Map<Integer, 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 )
