连续数组
题面
leetcode题目
给定一个二进制数组 \(nums\) , 找到含有相同数量的 \(0\) 和 \(1\) 的最长连续子数组，并返回该子数组的长度。
example
输入: \(nums = [0,1]\)
输出: \(2\)
说明: \([0, 1]\) 是具有相同数量0和1的最长连续子数组。
数据范围
- \(1 <= nums.length <= 10^5\)
- \(nums[i]\) 不是 \(0\) 就是 \(1\)
题解
总体思路
这个题目都想不到前缀和维护就太离谱了。
为了方便我们令下标从1开始计算，维护\(sum_1[i]\)表示\(nums[1],nums[2],nums[3]\cdots nums[i]\)中\(1\)的个数，那么很自然的 \[sum_0[i] = i - sum_1[i] \tag{1}\] 题目要求 \[ sum_1[i] - sum_1[j] = sum_0[i] - sum_0[i] \tag{2}\] 我们合并\((1)\)和\((2)\)式，可以得到: \[ sum_1[i] -sum_1[j] = i - sum_1[i] - j + sum_1[j] \tag{3}\] 很自然的，我们需要探求\(sum_1[i]\)与\(sum_1[j]\)的关系，所以我们这样整理式子: \[ 2\times sum_1[i] - i = 2\times sum_1[j] -j \tag{4}\] 由\((4)\)式我们可知，满足此条件的\(i\)和\(j\)之间构成的子数组(注意不含j)，满足题目要求，显然我们可以维护一个哈希表来表示最远端的满足\((4)\)式的值。
代码
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;
#define _DEBUG
class Solution
{
public:
int findMaxLength(vector<int> &nums)
{
int len = nums.size();
int sum[len + 1];
sum[0] = 0;
map<int, int> idxMap;
idxMap[0] = 0;
int max = 0;
for (int i = 1; i <= len; i++)
{
int num = nums[i - 1];
if (num == 1)
{
sum[i] = sum[i - 1] + 1;
}
else
{
sum[i] = sum[i - 1];
}
int tmp = 2 * sum[i] - i;
#ifdef _DEBUG
cout << "i: " << i << " sum[i]: " << sum[i] << " tmp: " << tmp << endl;
#endif
if (idxMap.count(tmp) != 0)
{
int preIdx = idxMap[tmp];
int subLen = i - preIdx;
if (subLen > max)
{
max = subLen;
}
}
else
{
idxMap[tmp] = i;
}
}
return max;
}
};
int main()
{
Solution s;
vector<int> nums1{0, 1};
cout << s.findMaxLength(nums1) << endl;
vector<int> nums2{0, 1, 0};
cout << s.findMaxLength(nums2) << endl;
return 0;
}
|