未排序数组中累加和为给定值的最长子数组系列问题

题目

给定一个无序数组 arr，其中元素可正、可负、可 0。给定一个整数 k，求 arr 所有的子数组中累加和为 k 的最长子数组长度。

补充问题 1：给定一个无序数组 arr，其中元素可正、可负、可 0。求 arr 所有的子数组中正数与负数个数相等的最长子数组长度。

补充问题 2：给定一个无序数组 arr，其中元素只是 1 或 0。求 arr 所有的子数组中 0 和 1 个数相等的最长子数组长度。

解答

这题的主要思想是利用了这样一个数据 s(i))，其中，i 表示数组的索引，s(i) 表示从数组开头累加到 i 索引处的累加值。

其次，使用了哈希表这一数据结构，我们用 map 来表示，map 里存储的就是存储第一次出现的 s(i) 以及 i。这里要注意的一点就是 map 中键为 0 的键值对中存储的值是 -1，表示起始时 s(i) 为 0。

代码

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
// 原问题
public int getMaxLength(int[] arr, int k) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    // map 的 key 是 sum，i 是 s(i)，即从索引为 0 处一直累加到 i 处的值的结果
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1); // 下标从 -1 开始，初始时，放进 map 中的 sum 为 0
    int len = 0;
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
        // 这里相当于以 i 为终点，向前寻找最远的满足 arr[j..i] 的累加和为 k 的索引 j
        if (map.containsKey(sum - k)) {
            len = Math.max(i - map.get(sum - k), len);
        }
        // 如果 map 中没有包含 sum，那就加入，否则不作任何操作，这样
        // 可以保证 map 中存储的 i 是使得 s(i) 的值为 sum 的最小的索引
        if (!map.containsKey(sum)) {
            map.put(sum, i);
        }
    }
    return len;
}
// 补充问题 1
public int getMaxLength_2(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[0] == 0) {
            continue;
        }
        arr[i] = arr[i] < 0 ? -1 : 1;
    }
    return getMaxLength(arr, 0);
}
// 补充问题 2
public int getMaxLength_3(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        arr[i] = arr[i] == 0 ? -1 : 1;
    }
    return getMaxLength(arr, 0);
}

测试

1
2
3
4
5
6
public static void main(String[] args) {
    int[] arr = {1, 2, 3, 1, 1, 1, 1, 2, 3};
    // 测试
    GetMaxLength_10 gml = new GetMaxLength_10();
    System.out.println(gml.getMaxLength(arr, 6));
}

输出

5