个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创前缀和(7)_连续数组
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目链接 :
2. 题目描述 :
3. 解法(一维前缀和) :
算法思路 :
示例说明:
代码展示 :
结果分析:
1. 题目链接 :
OJ链接: 连续数组
2. 题目描述 :
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1:
输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:
输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
提示：
1 <= nums.length <= 105nums[i]不是0就是1
3. 解法(一维前缀和) :
算法思路 :
转换 0 和 1：
将 0 视作 - 1，而 1 保持不变。这意味着在计算前缀和时，0 会减少总和。
这样，当某段区间内的 0 和 1 数量相同时，前缀和将回到相同的值。
计算前缀和：
遍历数组时，维护一个变量 sum 用来表示当前的前缀和。
如果在某个位置的 sum 值与之前某个位置的 sum 值相同，说明从这两个位置之间的元素（即子数组）中，0 和 1 的数量相等。
使用哈希表记录前缀和的索引：
使用一个哈希表 dp 来存储每个前缀和第一次出现的索引。
初始化 dp[0] = -1，表示前缀和为 0 的情况下，虚拟的索引是 - 1，这有助于处理从数组起始位置开始的有效子数组。
判断条件：
在遍历数组时，每当计算新的前缀和 sum：
如果 sum 已经在 dp 中存在（即 dp.count(sum) 为真），这意味着从 dp[sum] + 1 到当前索引 i 的这段区间中，0 和 1 的数量相等。
通过计算当前索引 i 与 dp[sum] 的差值得到这段子数组的长度：i - dp[sum]。
示例说明:
假设有一个数组 nums = [0, 1, 0, 1]，我们可以按以下步骤分析前缀和的变化：
初始状态：
dp = { 0: -1 }
sum = 0
ret = 0
遍历数组：
i = 0, nums[0] = 0:
sum = 0 + (-1) = -1
dp[-1] 不存在，所以将 dp[-1] = 0。
i = 1, nums[1] = 1 :
sum = -1 + 1 = 0
dp[0] 已存在，表示从 dp[0] + 1 到 i 的子数组有相同数量的 0 和 1，长度为 1 - (-1) = 2，更新 ret = 2。
i = 2, nums[2] = 0 :
sum = 0 + (-1) = -1
dp[-1] 已存在，长度为 2 - 0 = 2，ret 不变。
i = 3, nums[3] = 1 :
sum = -1 + 1 = 0
dp[0] 已存在，长度为 3 - (-1) = 4，更新 ret = 4。
代码展示 :
class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> dp;dp[0] = -1;int sum = 0, ret = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;if(dp.count(sum)) ret = max(ret, i - dp[sum]);else dp[sum] = i;} return ret;}
};
结果分析:
时间复杂度和空间复杂度
时间复杂度 :O(n)，其中n 是数组的长度。我们只遍历数组一次。
空间复杂度 :O(n)，在最坏情况下，哈希表可能存储所有的前缀和。