求解思路
这道题我们先对数组进行预处理,将正数统一变为1,负数统一变为-1,零保持不变。
如果两个位置的前缀和相等,那么这两个位置之间的子数组和必然为0。因此，我们用哈希表记录每个前缀和第一次出现的位置,当再次遇到相同前缀和时,就能计算出一个和为0的子数组长度,遍历过程中不断更新最大值。
注意要在哈希表中预设sum=0对应位置-1,这样可以正确处理从数组开头开始的子数组。
举个栗子
输入数组:[1, -1, 2, -2, 3]
预处理后:[1, -1, 1, -1, 1]
- 位置0: sum=1, 记录{1→0}
- 位置1: sum=0, 已存在{0→-1}, 长度=1-(-1)=2
- 位置2: sum=1, 已存在{1→0}, 长度=2-0=2
- 位置3: sum=0, 已存在{0→-1}, 长度=3-(-1)=4
- 位置4: sum=1, 已存在{1→0}, 长度=4-0=4
最长长度为4,对应子数组[-1, 2, -2, 3]。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.io.*;
import java.util.HashMap;
public class Main{
public static int MAXN = 100001;
public static int[] arr = new int[MAXN];
public static int n;
public static HashMap<Integer, Integer> map = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in = new StreamTokenizer(br);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
while (in.nextToken() != StreamTokenizer.TT_EOF) {
n = (int) in.nval;
for (int i = 0, num; i < n; i++) {
in.nextToken();
num = (int) in.nval;
// 预处理:正数变1,负数变-1,零保持0
arr[i] = num != 0 ? (num > 0 ? 1 : -1) : 0;
}
out.println(compute());
}
out.flush();
out.close();
br.close();
}
public static int compute() {
map.clear();
map.put(0, -1); // 初始化:前缀和为0对应位置-1
int ans = 0;
for (int i = 0, sum = 0; i < n; i++) {
sum += arr[i]; // 累加前缀和
if (map.containsKey(sum)) {
// 找到相同前缀和,计算子数组长度
ans = Math.max(ans, i - map.get(sum));
} else {
// 第一次出现该前缀和,记录位置
map.put(sum, i);
}
}
return ans;
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~