题目
给你一个二进制数组 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 <= 10^5nums[i]要么是0要么是1。
解题思路
这道题可以转化为一个更简单的问题：找到一个最长的子数组，它里面最多只包含一个 0。
为什么是这样？因为题目要求我们删除一个元素，使得剩下的子数组只包含 1。
- 如果我们找到一个子数组，它只包含 1，那么我们必须删除其中的一个 1，剩下的最长子数组长度为
(原始长度 - 1)。 - 如果我们找到一个子数组，它包含一个 0，比如
[1,1,0,1,1]，我们删除这个 0，那么剩下的子数组就变成了[1,1,1,1]，长度为(原始长度 - 1)。
所以，无论是删除一个 1 还是删除一个 0，我们最终得到的全 1 子数组的长度，都等于原始子数组的长度减一。
因此，思路就是用滑动窗口来找到一个最长的子数组，这个子数组中包含的 0 的数量不超过 1。
具体思路
- 初始化变量：
left = 0, right = 0: 滑动窗口的左右边界。n = nums.size(): 数组长度。haveZero = 0: 记录当前窗口内 0 的数量。ans = 0: 存储找到的最长子数组的长度。
- 扩展窗口：
for(right; right < n; right++): 右指针right从 0 开始向右移动，不断扩大窗口。if(nums[right] == 0) haveZero++;: 每当右指针right遇到一个 0，haveZero计数器就加 1。
- 收缩窗口：
while(haveZero > 1): 当窗口内的 0 的数量超过 1 个时，这个窗口不再符合要求（最多只能有一个 0）。if(nums[left] == 0) haveZero--;: 此时需要收缩窗口，将左指针left向右移动。如果left指向的元素是 0，说明我们移除一个 0，haveZero计数器减 1。left++;: 左指针left向右移动一位。- 这个
while循环会一直执行，直到窗口内 0 的数量重新回到 1 或 0。
- 更新结果：
ans = max(ans, right - left);: 每次循环结束后，当前窗口[left, right]都满足“最多包含一个 0”的条件。这个窗口的长度是(right - left + 1)。- 因为我们必须删除一个元素，所以最终全 1 子数组的长度是
(right - left + 1) - 1，也就是(right - left)。 - 我们取所有符合条件的窗口长度
(right - left)中的最大值，更新到ans。
- 返回结果：
return ans;: 循环结束后，ans中存储的就是最终的最长全 1 子数组的长度。
具体代码
class Solution {
public:
int longestSubarray(vector<int>& nums) {
int left = 0;
int right = 0;
int n = nums.size();
int haveZero = 0;
int ans = 0;
for(right; right < n; right++)
{
if(nums[right] == 0)
haveZero++;
while(haveZero > 1)
{
if(nums[left] == 0)
haveZero--;
left++;
}
ans = max(ans, right - left);
}
return ans;
}
};
复杂度分析
时间复杂度: O(n)
代码的核心是一个滑动窗口，由 left 和 right 两个指针构成。
right指针：外层的for循环从头到尾遍历了一遍数组，所以right指针总共移动了n次，其中n是数组nums的长度。left指针：内层的while循环会移动left指针。虽然看起来是嵌套循环，但left指针也只可能从头到尾移动一遍，它不会向后退。
每个元素最多被 right 指针访问一次，也最多被 left 指针访问一次。因此，总的操作次数与数组的长度 n 成线性关系。所以，时间复杂度是 O(n)。
空间复杂度: O(1)
代码在运行过程中只使用了几个固定的变量 (left, right, n, haveZero, ans) 来存储状态。这些变量所占用的空间是恒定的，不随输入数组 nums 的大小而改变。因此，空间复杂度是 O(1)。