专栏：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算法文档 。