LeetCode525-连续数组

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/contiguous-array/

中文链接：https://leetcode-cn.com/problems/contiguous-array/

题目详述

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:

输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

题目详解

  • LeetCode560-和为K的子数组 是求和为 K 的子数组个数，而本题可以转化为求和为 K 的子数组的最大长度。
  • 如果我们把 0 变成 -1，本题就变成了求和为 0 的子数组的最大长度。
  • 如果知道求和为 K 的子数组的最大长度，解答本题就很容易了。
  • 思路：对数组求前缀和，这样连续子数组的和就可以用两个前缀和之差算出来。
  • 为了计算长度，用一个 Map 记录每个前缀和最早出现的下标。
  • 遍历数组，假设当前前缀和为 s，在 map 中查找前缀和为 s - k 的出现次数，加入到结果中。
  • 为了计算正确，map 在初始时要放入一个代表前缀和为 0、下标为 -1 的键值对。
  • 时间复杂度为 O(n)，空间复杂度为 O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMaxLength(int[] nums， int k) {
    Map<Integer, Integer> map = new HashMap<>();
    // 初始时放入一个代表前缀和为 0、下标为 -1 的键值对
    map.put(0, -1);
    int res = 0;
    int s = 0;
    for (int i = 0; i < nums.length; ++i) {
        s += nums[i];
        if (map.containsKey(s - k)) {
            res = Math.max(res, i - map.get(s - k));
        }
        map.putIfAbsent(s, i);
    }
    return res;
}

有了上面的结论，解答本题就很容易了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00525 {

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        // 初始时放入一个代表前缀和为 0、下标为 -1 的键值对
        map.put(0, -1);
        int res = 0;
        int s = 0;
        for (int i = 0; i < nums.length; ++i) {
            s += nums[i] == 1 ? 1 : -1;
            if (map.containsKey(s)) {
                res = Math.max(res, i - map.get(s));
            } else {
                map.put(s, i);
            }
        }
        return res;
    }
}