【大战蓝桥杯】 算法·每日一题（详解+多解）-- day10
✨博主介绍
0 和 1 个数相同的子数组
解题思路
💫点击直接资料领取💫
✨博主介绍
🌊 作者主页：苏州程序大白
🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司
💬如果文章对你有帮助，欢迎关注、点赞、收藏
💅 有任何问题欢迎私信，看到会及时回复
💅关注苏州程序大白，分享粉丝福利
0 和 1 个数相同的子数组
给定一个二进制数组 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 <= 105 nums[i] 不是 0 就是 1
解题思路
错误的思路：滑动窗口，双指针
一开始打算运用双指针的想法，但是就实际而言是难以行通的。
对于[0,0,0,1,1,1,0]最后可能为误判为0。但是实际是6
总结一下，当不能明确得知可以淘汰的某些值时候就最好不要使用双指针。
前面那些0并不能直接判断是否需要淘汰,需要根据后面很多数来确定
public int findMaxLength(int[] nums) { int res=0; int n=nums.length; int slow=0, fast=0; int zeroNum=0, oneNum=0; while (fast<n){ for (int i=0; i<2 && fast<n; i++){ if (nums[fast++]==0) zeroNum++; else oneNum++; } if (oneNum==zeroNum) res = Math.max(res, fast-slow); else { if (nums[slow++]==0) zeroNum--; else oneNum--; } } return res; }
前缀和+哈希表
把0当做-1处理，这里就转变为了求和为0的子数组的问题
key=前缀和，value=第一次出现过的位置
遍历数组，记录某个前缀和第一次出现的位置，设置初始值为map[0] = -1
当前缀和sum在此前出现过，则说明这两个前缀和区间差构成的所有元素和为0，满足条件更新res的值，否则记录到map中
class Solution { public int findMaxLength(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); map.put(0, -1); int sum = 0, res = 0; for (int i = 0; i < nums.length; ++i) { sum += nums[i] == 1 ? 1 : -1; if (map.containsKey(sum)) { res = Math.max(res, i - map.get(sum)); } else { map.put(sum, i); } } return res; } }
