1. 题目解析

题目链接：525. 连续数组

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

核心在于计算题目所给数组是否存在连续子数组使得数组里头0和1的数量相同，存在返回连续子数组最长长度即可，不存在返回0即可。

2.算法原理

稍微转化一下题目，我们可以将其转化为一个更熟悉的问题：

• 本题要求找出一段连续的区间，使得其中0和1出现的次数相同。
• 如果我们将0视为-1，1视为1，那么问题就转化为寻找一段区间，使得这段区间的和等于0。
• 这个问题与“和为K的子数组”的思路相似，即通过前缀和和哈希表来寻找符合条件的子数组。

具体解题思路如下：

1. 设定变量与数据结构：
   • 设i为数组中的任意位置。
   • sum[i]表示从数组起始位置到位置i（包括i）之间所有元素（将0视为-1，1视为1）的和。
   • 使用一个哈希表来存储每个前缀和第一次出现的位置。
2. 遍历数组并计算前缀和：
   • 遍历数组，同时计算当前位置的前缀和sum[i]。
   • 在遍历过程中，不断更新哈希表，记录每个前缀和第一次出现的位置。
3. 查找符合条件的子数组：
   • 对于每个位置i，检查哈希表中是否存在键为sum[i]的项。
   • 如果存在，说明在位置i之前存在一个位置x1，使得区间[x1, i]的和为0（即0和1的数量相同）。
   • 记录i - x1的值，这表示以i为结尾的符合条件的子数组的长度。
   • 更新最大长度（如果需要的话）。
4. 注意事项：
   • 不需要真正初始化一个完整的前缀和数组，因为只关心在位置i之前，前缀和等于sum[i]的位置。
   • 哈希表用于存储前缀和及其第一次出现的位置，这样可以在O(1)的时间内查找到符合条件的位置。

3.代码编写

class Solution 
{
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;//前缀和和下标的关系hash[0] = -1;//默认前缀和为零时下标时-1int ret = 0, sum = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;if(hash.count(sum)) ret = max(ret, i - hash[sum]);else hash[sum] = i;}return ret;}
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~