求解思路
这道题，维护一个累加和sum，对于当前位置i，如果存在某个更早的位置j使得从j+1到i的子数组和等于aim，那么必然有sum[i] - sum[j] = aim，即sum[j] = sum[i] - aim。
用哈希表记录每个前缀和第一次出现的位置，遍历数组时检查sum - aim是否在哈希表中，如果存在就计算子数组长度并更新答案。
这里有个细节：初始化时把(0, -1)放入哈希表，表示"什么都不选时前缀和为0"，这样当从数组开头就满足条件时也能正确计算。
另外，每个前缀和只记录最早出现的位置，因为要求的是最长子数组，起点越早长度越大。
举例说明
输入：arr = [1, 2, 3, -2, 5]，aim = 5
- i=0: sum=1, 查找-4不存在，记录(1,0)
- i=1: sum=3, 查找-2不存在，记录(3,1)
- i=2: sum=6, 查找1存在于位置0，长度=2-0=2，记录(6,2)
- i=3: sum=4, 查找-1不存在，记录(4,3)
- i=4: sum=9, 查找4存在于位置3，长度=4-3=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
46
47
48
49
|
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, aim;
// key : 某个前缀和
// value : 这个前缀和最早出现的位置
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;
in.nextToken();
aim = (int) in.nval;
for (int i = 0; i < n; i++) {
in.nextToken();
arr[i] = (int) in.nval;
}
out.println(compute());
}
out.flush();
out.close();
br.close();
}
public static int compute() {
map.clear();
// 前缀和0在-1位置，表示一个数都不取
map.put(0, -1);
int ans = 0;
for (int i = 0, sum = 0; i < n; i++) {
sum += arr[i];
// 如果存在前缀和为sum-aim，说明中间部分和为aim
if (map.containsKey(sum - aim)) {
ans = Math.max(ans, i - map.get(sum - aim));
}
// 只记录每个前缀和最早出现的位置
if (!map.containsKey(sum)) {
map.put(sum, i);
}
}
return ans;
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~