来到 arr[4]=1 ，放入 (14,4) ， sum-aim=7 ，发现 HashMap 中有 key=7 的记录 (7,0) ，即在0位置上累
加和就能达到7了，因此 1~4 是以下标为4结尾的子数组中累积和为 7 的最长子数组，更新
maxLength=4 。 ->(14,4)
来到 arr[5]=7 ，放入 (21,5) ， sum-aim=14 ， HashMap 中有 (14,4) ，因此 5~5 是本轮的最长子数
组，但 maxLength=4>1 ，因此不更新。 ->(21,5)
来到 arr[6]=-6 ，放入 15,6 ，没有符合的子数组。 ->(15,6)
来到 arr[7]=-1 ，累加和为 15+(-1)=14 ，但 HashMap 中有 key=14 的记录，因此不放入 (14,7)
（ HashMap 中保存的是某累加和第一次出现的位置，而14这个了累加和最早在4下标上就出现了）。 sum-
aim=7 ， HashMap 中有 (7,0) ，因此本轮最长子数组为 1~7 ，因此更新 maxLength=7 。
来到 arr[8]=7 ，累加和为21，存在key为21的记录，因此不放入（21，7）。 sum-aim=14 ，本轮最长子数
组为 5~8 ，长度为4，不更新 maxLength 。
示例代码：
拓展
求奇数个数和偶数个数相同的最长子数组长度
将奇数置为1，偶数置为-1，就转化成了求和为0的最长子数组长度
求数值为1的个数和数值为2的个数相同的最长子数组（数组只含0、1、2三种元素）
将2置为-1，就转化成了求和为0的最长子数组长度
public static int maxLength(int[] arr,int aim) {
//key->accumulate sum value->index
HashMap<Integer, Integer> hashMap = new HashMap<>();
hashMap.put(0, -1);
int curSum = 0;
int maxLength = 0;
for (int i = 0; i < arr.length; i++) {
curSum += arr[i];
if (!hashMap.containsKey(curSum)) {
hashMap.put(curSum, i);
}
int gap = curSum - aim;
if (hashMap.containsKey(gap)) {
int index = hashMap.get(gap);
maxLength = Math.max(maxLength, i - index);
}
}
return maxLength;
}
public static void main(String[] args) {
int arr[] = {7, 3, 2, 1, 1, 7, -6, -1, 7};
int aim = 7;
System.out.println(maxLength(arr, aim));//7
}
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
剩余112页未读，继续阅读
