题目描述
给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点最小的。若不存在这样的数组，返回一个空数组。
示例 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"]
输出: []
提示：
解法
方法一：前缀和 + 哈希表
题目要求找到最长的子数组，且包含的字符和数字的个数相同。我们可以将字符看作 \(1\)，数字看作 \(-1\)，那么问题就转化为：求最长的子数组，使得该子数组的和为 \(0\)。
我们可以运用前缀和的思想，用哈希表 \(vis\) 记录每个前缀和第一次出现的位置，用变量 \(mx\) 和 \(k\) 分别记录最长的满足条件的子数组的长度和左端点位置。
接下来遍历数组，计算当前位置 \(i\) 的前缀和 \(s\)：
- 如果当前位置的前缀和 \(s\) 在哈希表 \(vis\) 中存在，我们记第一次出现 \(s\) 的位置为 \(j\)，那么区间 \([j + 1,..,i]\) 的子数组和就为 \(0\)。如果此前的最长子数组的长度小于当前子数组的长度，即 \(mx \lt i - j\)，我们就更新 \(mx = i - j\) 和 \(k = j + 1\)。
- 否则，我们将当前位置的前缀和 \(s\) 作为键，当前位置 \(i\) 作为值，存入哈希表 \(vis\) 中。
遍历结束后，返回左端点为 \(k\)，且长度为 \(mx\) 的子数组即可。
时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
vis = {0: -1}
s = mx = k = 0
for i, x in enumerate(array):
s += 1 if x.isalpha() else -1
if s in vis:
if mx < i - (j := vis[s]):
mx = i - j
k = j + 1
else:
vis[s] = i
return array[k : k + mx]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public String[] findLongestSubarray(String[] array) {
Map<Integer, Integer> vis = new HashMap<>();
vis.put(0, -1);
int s = 0, mx = 0, k = 0;
for (int i = 0; i < array.length; ++i) {
s += array[i].charAt(0) >= 'A' ? 1 : -1;
if (vis.containsKey(s)) {
int j = vis.get(s);
if (mx < i - j) {
mx = i - j;
k = j + 1;
}
} else {
vis.put(s, i);
}
}
String[] ans = new String[mx];
System.arraycopy(array, k, ans, 0, mx);
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public:
vector<string> findLongestSubarray(vector<string>& array) {
unordered_map<int, int> vis{{0, -1}};
int s = 0, mx = 0, k = 0;
for (int i = 0; i < array.size(); ++i) {
s += array[i][0] >= 'A' ? 1 : -1;
if (vis.count(s)) {
int j = vis[s];
if (mx < i - j) {
mx = i - j;
k = j + 1;
}
} else {
vis[s] = i;
}
}
return vector<string>(array.begin() + k, array.begin() + k + mx);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func findLongestSubarray(array []string) []string {
vis := map[int]int{0: -1}
var s, mx, k int
for i, x := range array {
if x[0] >= 'A' {
s++
} else {
s--
}
if j, ok := vis[s]; ok {
if mx < i-j {
mx = i - j
k = j + 1
}
} else {
vis[s] = i
}
}
return array[k : k+mx]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function findLongestSubarray(array: string[]): string[] {
const vis = new Map();
vis.set(0, -1);
let s = 0,
mx = 0,
k = 0;
for (let i = 0; i < array.length; ++i) {
s += array[i] >= 'A' ? 1 : -1;
if (vis.has(s)) {
const j = vis.get(s);
if (mx < i - j) {
mx = i - j;
k = j + 1;
}
} else {
vis.set(s, i);
}
}
return array.slice(k, k + mx);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
func findLongestSubarray(_ array: [String]) -> [String] {
var vis: [Int: Int] = [0: -1]
var s = 0, mx = 0, k = 0
for i in 0..<array.count {
s += array[i].first!.isLetter ? 1 : -1
if let j = vis[s] {
if mx < i - j {
mx = i - j
k = j + 1
}
} else {
vis[s] = i
}
}
return Array(array[k..<(k + mx)])
}
}
|