README.md

面试题 17.05. 字母与数字

English Version

题目描述

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

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

示例 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

解法

前缀和 + 哈希表。

遍历字符串数组 array，将数字视为 1，字母视为 -1（或者反过来），题目转换为元素和为 0 的最长子数组。

Python3

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        seen = {0: -1}
        t = mx = 0
        ans = []
        for i, s in enumerate(array):
            t += 1 if s.isalpha() else -1
            if t in seen:
                if mx < i - seen[t]:
                    mx = i - seen[t]
                    ans = array[seen[t] + 1: i + 1]
            else:
                seen[t] = i
        return ans

Java

class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, -1);
        int t = 0, mx = 0;
        int j = 0;
        for (int i = 0; i < array.length; ++i) {
            t += Character.isDigit(array[i].charAt(0)) ? 1 : -1;
            if (seen.containsKey(t)) {
                if (mx < i - seen.get(t)) {
                    mx = i - seen.get(t);
                    j = seen.get(t) + 1;
                }
            } else {
                seen.put(t, i);
            }
        }
        String[] ans = new String[mx];
        for (int i = 0; i < mx; ++i) {
            ans[i] = array[i + j];
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        unordered_map<int, int> seen;
        seen[0] = -1;
        int t = 0, mx = 0, j = 0;
        for (int i = 0; i < array.size(); ++i)
        {
            t += isdigit(array[i][0]) ? 1 : -1;
            if (seen.count(t))
            {
                if (mx < i - seen[t])
                {
                    mx = i - seen[t];
                    j = seen[t] + 1;
                }
            }
            else
            {
                seen[t] = i;
            }
        }
        return {array.begin() + j, array.begin() + j + mx};
    }
};

Go

func findLongestSubarray(array []string) []string {
	seen := map[int]int{0: -1}
	t, mx, j := 0, 0, 0
	for i, s := range array {
		if unicode.IsDigit(rune(s[0])) {
			t++
		} else {
			t--
		}
		if k, ok := seen[t]; ok {
			if mx < i-k {
				mx = i - k
				j = k + 1
			}
		} else {
			seen[t] = i
		}
	}
	return array[j : j+mx]
}

...