LeetCode 525. Contiguous Array
先看题目:
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
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 number of given pairs will be in the range [1, 1000].
给出一个长度在0到1000内的数组,数组只由0和1组成,找出一个最大的连续子数组,数组中0和1的个数相同。返回这个数组的长度。
我一开始动态规划的解法,但是很难去写出状态转移方程。而且DP的解法至少也要O(n2),并不容易适用。
这里有一种巧妙的解法,对于一个数组A,如果第 i 个元素到第 j 个元素是一个0 1 个数相同的数组的话那么 0到 i - 1 中0 1个数的差值和 0 到 j 中 0 1次数的差值,
是相等的。我们可以通过一次遍历,存储所有差值,使用数组存储。然后找出数组里值相同的下标差最大的,也就是距离最远的两个元素就可以了。
对于找出最远元素的方法,一开始并没有特别的思考,觉得只是单纯的遍历就可以了。这样时间复杂度就是O(n2),但我发现在我还是too young too simple
提交了发现爆了时间
所以还是要降低时间复杂度。
优化找出最远元素的部分。
我们可以这样: 新建一个数组 M,M用来存储与差值对应的下标,具体地说:M是一个大小 2 * n + 1的数组,因为差值的取值是从 -n 到 n ,对于每一个差值 M [ n ] == 第一次出现差值为n的下标,这样只要遍历数组的时候实时更新最大长度就可以了。所以时间复杂度为O(n)。
经过改进后 速度超过了96%的submission。
其实还可以使用map的,使用map存储,但一般要比这样慢一些。
附java实现代码:
https://github.com/1163710128/LeetCode/blob/master/LeetCode525ContiguousArray.java