力扣练习——68 连续数组

68 连续数组

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

示例 1:

输入: [0,1]

输出: 2

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

示例 2:

输入: [0,1,0]

输出: 2

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

注意: 给定的二进制数组的长度不会超过50000。
2.输入说明
首先输入二进制数组的长度n，

然后输入n个0或1，以空格分隔
3.输出说明
输出一个整数，表示结果
4.范例
输入
7
0 0 1 1 0 0 1
输出
6
5.代码

#include
#include
#include
#include
#include
#include
#include
#include 

using namespace std;

int findMaxLen(vector<int> nums)
{
	int n = nums.size();
	//因为题目要求0和1的数量相等，为了方便判断，将所有0转化为-1，那么只要前缀和为0的情况，就是0和1数量相等的情况
	vector<int>newnums;
	int tmp;
	for (int t : nums)
	{
		if (t == 0)
			tmp = -1;
		else
			tmp = 1;
		newnums.push_back(tmp);
	}
	
	unordered_map<int, int>presum;//第一个int代表前缀和  ，第二个int代表出现的位置
	
	presum[0] = -1;  //默认空的前缀和为 0  ，出现的位置为-1
	
	int maxLength = 0;
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		//统计前缀和
		sum += newnums[i];
		
		if (presum.count(sum) > 0)//在哈希表中找该前缀和sum是否已经存在
		{
			int preIndex = presum[sum];//该前缀和sum的下标 为preIndex    ,而因为当前的前缀和已经在哈希表中存在 ，就可以计算前缀和为0的子数组长度[两者下标的差值]
			maxLength = max(maxLength, i - preIndex);
		}
		else
			presum[sum] = i;//记录该前缀和sum  ，以及出现的下标i
	}
	//要注意，哈希表的对应条件 (key,val) 每个key值是唯一的 ，而且和val一一对应，但是val值可以存在相等的情况
	
	return maxLength;
}



int main()

{
	int n,tmp;
	cin >> n;
	vector<int>nums;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp;
		nums.push_back(tmp);
	}
	int res = findMaxLen(nums);
	cout << res << endl;
	return 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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70