专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一郑州轻工业大学的学生找了一份实习的工作，HR给出了高达一千的月薪，并且在实习生考核优秀的情况下才会有，不优秀的情况下一毛钱都没有，只报销回去的路费。郑州轻工业大学虽然不是什么名校，但C++开发一个月最高才能拿到1000块钱的薪资，这也太侮辱人了。看这HR聊天的态度估计最多也只能拿个路费，并且还要干满一个月，如果不到一个月，连路费都没有，即便是在十多年前也没见过这么无耻的公司，还去干啥啊。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第525题：连续数组。
问题描述
来源：LeetCode第525题
难度：中等
给定一个二进制数组 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 <= 10^5
nums[i] 不是 0 就是 1
问题分析
这题实际上是让求一个最长的子数组，并且这个子数组中 0 和 1 的数量必须相同。 因为数组中的元素只能是 0 或 1 ，直接计算不太好解，我们可以换种思路， 把数组中的 0 换成 -1 。
这样 0 和 1 的数量必须相同就变成了 -1 和 1 的数量必须相同了，它们相加的结果肯定是 0 ，所以这题 就变成了求一个最长的子数组，并且这个子数组的和必须是0 。
我们以示例2为例来看下，改变之后的数组就变成了[-1,1,-1]。那么这题的解题思路就很明确了，我们可以直接使用前缀和，对改变之后的数组进行累加，然后使用一个map对累加的值进行存储， 因为是求最大长度，如果遇到相同的值则不能覆盖 。
关于前缀和的知识以及求最大长度，最小长度还有求频率的总结，大家可以参考我书中 的10.3.3节，这里就不在过多介绍。
累加的时候如果出现相同的值，只需要用当前值的下标减去前面相同值的下标，中间这段就是和为0的子数组，我们只需要保存它的长度，记录最大值即可。
这里还要注意使用map存储前缀和的时候，要考虑 0 的情况，也就是说如果从数组的第一个元素到当前元素nums[i]的和是 0 ，那么这个长度就是 i+1，因为数组的下标是从0开始的，所以这 里前缀和为 0 的时候，我们给它一个默认值 -1 。
JAVA：
public int findMaxLength(int[] nums) { Map
map = new HashMap<>(); map.put( 0, -1); // 前缀和为0的时候，给一个默认值-1。 int preSum = 0, max = 0; for ( int i = 0; i < nums.length; i++) { // 计算前缀和，原数组中如果是0，就让它变成-1。 preSum += nums[i] == 0 ? -1 : 1; if ( map.containsKey(preSum)) { // 如果出现相同的前缀和，就计算长度，并保存最大值。 max = Math.max(max, i - map.get(preSum)); } else { // 如果没有出现相同的前缀和，就把它存起来。 map.put(preSum, i); } } return max; }C++:
public: int findMaxLength(vector
& nums) { unordered_map
mp ; mp[0]= -1;// 前缀和为0的时候，给一个默认值-1。 int preSum = 0, maxLength = 0; for (int i = 0; i < nums.size(); i++) { // 计算前缀和，原数组中如果是0，就让它变成-1。 preSum += nums[i] == 0 ? -1 : 1; if (mp.count(preSum)) { // 如果出现相同的前缀和，就计算长度，并保存最大值。 maxLength = max(maxLength, i - mp[preSum]); } else { // 如果没有出现相同的前缀和，就把它存起来。 mp[preSum]= i; } } return maxLength; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。