Leetcode 82 每个字符最多出现两次的最长子字符串 | 删掉一个元素以后全为 1 的最长子数组

1 题目

3090. 每个字符最多出现两次的最长子字符串

给你一个字符串s，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

示例 1：

输入：s = "bcbbbcba"

输出：4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入：s = "aaaa"

输出：2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

提示：

• 2 <= s.length <= 100
• s仅由小写英文字母组成。

2 代码实现

联想

和第三题的框架完全一致，先贴一个leetcode3的解法。

3. 无重复字符的最长子串

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char , int > window ; int left = 0 , right = 0 ; int res = 0 ; while (right < s.size()){ char c = s[right] ; right++; window[c]++; while (window[c] > 1 ){ char d = s[left]; left ++; window[d] --; } res = max (res,right - left); } return res; } };

本题做法：

class Solution { public: int maximumLengthSubstring(string s) { unordered_map<char , int >window; int left = 0 ; int right = 0; int res = 0 ; while (right < s.size()){ char c = s [right ]; right ++; window[c]++; while(window[c] > 2){ char d = s[left]; left ++; window[d]--; } res = max(res , right - left ); } return res; } };

总结

1. 收缩左边界的核心目的：让滑动窗口[left, right)重新回到无重复字符的状态，这是我们计算最长无重复子串长度的前提。
2. 收缩左边界的逻辑：从最左侧开始依次移出字符，直到当前重复的字符c的计数满足条件，此时窗口内不再有重复字符。
3. 整个滑动窗口的策略：右指针扩展窗口找新字符，左指针收缩窗口去重，过程中持续记录窗口的最大长度。

3 题目

1493. 删掉一个元素以后全为 1 的最长子数组

给你一个二进制数组nums，你需要从中删掉一个元素。

请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。

如果不存在这样的子数组，请返回 0 。

提示 1：

输入：nums = [1,1,0,1]输出：3解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 2：

输入：nums = [0,1,1,1,0,1,1,0,1]输出：5解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3：

输入：nums = [1,1,1]输出：2解释：你必须要删除一个元素。

提示：

• 1 <= nums.length <= 105
• nums[i]要么是0要么是1。

4 代码实现

思考

删掉一个0元素以后最长的全1数组长度，那么如果没有删除，就是一个数组最长，里面有且仅有一个0元素，其余都是1的元素。

思路：维护一个滑动窗口，只含有一个0，这个窗口最长的长度。

根本不需要和题目的操作一样顺着来这个先删除的操作，最后这个窗口的长度减去一就是答案了！

自己写的错误百出的代码

class Solution { public: int longestSubarray(vector<int>& nums) { unordered_map <int , int > window; int left = 0 ; int right = 0 ; int res = 0 ; while (right < nums.size()){ right ++; if (nums[right] == 1 ){ window[1]++; }else{ window[0]++; } while(window[0] == 1){ left ++; if(nums[left] == 1 ){ window[1]--; }else{ window[0]--; } } res = max(res , window[1] - 1); } return res ; } };

首先，明确你的核心需求

你想要实现的功能是：给定一个由 0 和 1 组成的数组，删除最多一个0（也可以不删）后，找到最长的连续 1 的子数组长度。

代码中存在的关键问题

1. 数组越界问题：right++执行后，直接访问nums[right]，当right达到nums.size()时，会访问到数组的越界位置，导致程序崩溃。
2. 收缩窗口的逻辑错误：while(window[0] == 1)的条件错误，应该是当窗口内的 0 的数量超过 1 时才收缩窗口（因为题目允许删除最多一个 0）。
3. 左指针移动后的计数错误：收缩窗口时，先执行left++再访问nums[left]，会漏掉对nums[left]初始位置的字符计数修改，导致window的计数不准确。
4. 结果计算错误：res = max(res, window[1] - 1)会错误地将 1 的计数减 1，正确的应该是直接取窗口内的有效长度（或window[1]，根据逻辑调整）。

修复后的完整代码

#include <vector> #include <unordered_map> #include <algorithm> using namespace std; class Solution { public: int longestSubarray(vector<int>& nums) { unordered_map<int, int> window; // 键：0或1，值：对应数字在窗口中的出现次数 int left = 0, right = 0; int res = 0; int max_ones = 0; // 记录窗口内1的最大数量 int zero_count = 0; // 窗口内0的数量（也可以用window[0]，单独变量更直观） while (right < nums.size()) { int num = nums[right]; right++; // 右指针扩展窗口 // 更新窗口内的计数 if (num == 1) { window[1]++; max_ones = max(max_ones, window[1]); // 记录1的最大数量 } else { window[0]++; zero_count++; } // 当窗口内0的数量超过1时，收缩左边界（因为最多只能删一个0） while (zero_count > 1) { int left_num = nums[left]; left++; // 左指针收缩窗口 // 更新计数 if (left_num == 1) { window[1]--; } else { window[0]--; zero_count--; // 关键：0的数量减1，退出循环的关键 } } // 计算当前窗口的有效长度：窗口长度（right-left）- 1（因为必须删除一个元素，即使是0） // 题目要求是“删除一个元素后”的长度，所以不管有没有0，都要减1 res = max(res, right - left - 1); } return res; } };

代码关键部分解释

1. 解决数组越界：先取nums[right]的值，再执行right++，避免访问越界的位置。
2. 收缩窗口的条件：当zero_count > 1时（窗口内有超过 1 个 0），收缩左边界，直到 0 的数量≤1（符合最多删一个 0 的要求）。
3. 计数更新逻辑：收缩左边界时，先取nums[left]的值，再执行left++，确保计数修改的是当前左指针指向的元素。
4. 结果计算：right - left - 1是删除一个元素后的窗口长度（题目要求必须删除一个元素，即使数组全是 1，也要删一个，比如[1,1,1]的结果是 2）。如果题目允许不删除元素（即最多删一个），则可以调整为max(res, zero_count == 0 ? right - left - 1 : right - left)。

测试用例

我们用几个例子验证代码的执行效果：

• 输入：nums = [1,1,0,1]
  • 过程：窗口会包含[1,1,0,1]（0 的数量 = 1），有效长度 = 4-1=3，结果为 3。
• 输入：nums = [0,1,1,1,0,1,1,0,1]
  • 有效长度为 5（比如窗口[1,1,1,0,1,1]，长度 6-1=5），结果为 5。
• 输入：nums = [1,1,1]
  • 有效长度 = 3-1=2，结果为 2。

自行修正后代码实现

class Solution { public: int longestSubarray(vector<int>& nums) { unordered_map <int , int > window; int left = 0 ; int right = 0 ; int res = 0 ; while (right < nums.size()){ int a = nums[right]; right ++; if (a == 1 ){ window[1]++; }else{ window[0]++; } while(window[0] > 1){ int b = nums[left]; left ++; if(b == 1 ){ window[1]--; }else{ window[0]--; } } res = max(res , right - left - 1); } return res ; } };

测试通过！

小结

好像感受到一些思路了，的确这种题目有固定的模板，也就是通用的解法，按照这个边总结边练习的方式刷题效果好了很多，加油(ง •_•)ง！！！