【每日一题Day143】面试题 17.05. 字母与数字 | 前缀和+哈希表

面试题 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)$