Leetcode 525 Contiguous Array

2020-04-15

题目链接

题目描述

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

1
2
3

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

1
2
3

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

解题思路（by others）

花花酱的讲解视频

问题一：如何判断数组中的 0 和 1 的个数相同？

对数组进行求和 sum，如果该项为 0 则 sum += -1，如果该项为 1 则 sum += 1
问题二：如何将时间复杂度缩短到 $O(n)$

如果是暴力求解，则是规定 $start \in [0, n - 1], end \in [0, n - 1]$, 计算 $[start, end]$ 区间中的和。然后这种解法的时间复杂度为 $O(n^3)$，可优化至 $O(n^2)$

假设存在一个区间 [i, j] 的和为 0，那么区间 [ 0, i - 1]之和与区间 [ 0, j ] 之和必然相同。因此，计算 [0, i] 区间之和，$i \in [0, n - 1]$, 如果该和第一次出现，则将其存储在 map 中，key 为和，value 为第一次出现的位置。如果该和并非第一次出现，则该和与第一次出现位置间的区间和必然为 0，计算该区间的长度，并与最大值比较。（与第一次出现位置间的区间长度必然大于之后每一次出现的区间长度，因此只需要记录第一次出现的区间位置）。这里要注意一个特例，如果该和为 0，则 [0, i] 区间本身便具有相同数量的 0 和 1，计算区间长度并与最大值比较。

具体解法：

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        
        unordered_map<int, int> prefix_map;
        
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) sum += -1;
            else sum += 1;
            if (sum == 0) {
                ans = i + 1;
                continue;
            }
            if (prefix_map.find(sum) == prefix_map.end()) {
                prefix_map[sum] = i;
            } else {
                int start = prefix_map[sum];
                int len = i - start;
                if (len > ans) ans = len;
            }
        }
        return ans;
    }
};

这里要注意 unordered_map 的查找 API

1 2	unordered_map<int, int> prefix_map; prefix_map.find(sum) == prefix_map.end(); //如果没有找到