其他系列文章导航
文章目录
前言
这是力扣的 1493 题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
又又又是一道滑动窗口的典型例题，可以帮助我们巩固滑动窗口算法。
这道题很活灵活现，需要加深对题意的变相理解。
一、题目描述
给你一个二进制数组 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 <= 105nums[i]要么是0要么是1。
二、题解
2.1 方法一：滑动窗口
思路与算法：
重点：题意转换。把「 返回最长的且只包含 1 的非空子数组的长度 」转换为 「 返回最长带有一个 0 的非空子数组的长度 - 1 」。
经过上面的题意转换，我们可知本题是求最大连续子区间，可以使用滑动窗口方法。滑动窗口的限制条件是：窗口内最多有 1 个 0。
可以使用我多次分享的滑动窗口模板解决，模板在代码之后。
再次申明模板很重要，可以解决一些列的题目。
首先定义四个变量：
- 左指针
- 右指针
- 最长的子串长度
- 0 的数量
编辑
代码思路：
- 使用 left 和 right 两个指针，分别指向滑动窗口的左右边界。
- right 主动右移：right 指针每次移动一步。当 nums[right] 为 0，说明滑动窗口内增加了一个 0；
- left 被动右移：判断此时窗口内 0 的个数，如果超过了 K，则 left 指针被迫右移，直至窗口内的 0 的个数小于等于 K 为止。
- 滑动窗口长度的最大值就是所求。记得最后要减去 1 ，因为子数组里还多了一个 0 。
编辑
2.2 滑动窗口解题模板
滑动窗口算法是一种常用的算法，用于解决数组或列表中的子数组问题。下面是一个滑动窗口算法的解题模板：
- 定义窗口大小：首先需要确定滑动窗口的大小，即每次滑动时包含的元素个数。
- 初始化窗口：将窗口的起始位置设置为0，窗口大小设置为n，其中n为数组或列表的长度。
- 计算窗口中的元素和：使用一个变量sum来记录当前窗口中的元素和，初始值为0。
- 移动窗口：从左到右依次遍历数组或列表，每次将当前元素加入窗口中，并更新sum的值。
- 判断是否满足条件：在移动窗口的过程中，不断判断当前窗口中的元素和是否满足题目要求。如果满足条件，则返回当前窗口中的元素和。
- 移动窗口：如果当前窗口中的元素和不满足题目要求，则将窗口向右移动一位，并更新sum的值。
- 重复步骤4-6，直到遍历完整个数组或列表。
下面是一个具体的例子，使用滑动窗口算法求解数组中连续子数组的最大和：
def maxSubArray(nums): if not nums: return 0 max_sum = current_sum = nums[0] for i in range(1, len(nums)): current_sum = max(nums[i], current_sum + nums[i]) max_sum = max(max_sum, current_sum) return max_sum
在这个例子中，我们使用一个变量max_sum来记录当前最大子数组的和，一个变量current_sum来记录当前窗口中的元素和。在遍历数组的过程中，不断更新current_sum的值，并判断是否满足题目要求。如果满足条件，则更新max_sum的值。最后返回max_sum即可。
三、代码
3.1 方法一：滑动窗口
Java版本：
class Solution { public int longestSubarray(int[] nums) { int left = 0, right = 0, zero = 0, longestSubarray = 0, n = nums.length; while (right < n) { if (nums[right] == 0) zero++; if (zero > 1) { left++; if (nums[left - 1] == 0) zero--; } if (zero == 1 || right == n - 1) { longestSubarray = Math.max(longestSubarray, right - left + 1); } right++; } return longestSubarray - 1; } }
C++版本：
class Solution { public: int longestSubarray(vector<int>& nums) { int left = 0, right = 0, zero = 0, longestSubarray = 0, n = nums.size(); while (right < n) { if (nums[right] == 0) zero++; if (zero > 1) { left++; if (nums[left - 1] == 0) zero--; } if (zero == 1 || right == n - 1) { longestSubarray = max(longestSubarray, right - left + 1); } right++; } return longestSubarray - 1; } };
Python版本：
class Solution: def longestSubarray(self, nums: List[int]) -> int: left = 0 right = 0 zero = 0 longestSubarray = 0 n = len(nums) while right < n: if nums[right] == 0: zero += 1 if zero > 1: left += 1 if nums[left - 1] == 0: zero -= 1 if zero == 1 or right == n - 1: longestSubarray = max(longestSubarray, right - left + 1) right += 1 return longestSubarray - 1
Go版本：
func longestSubarray(nums []int) int { left := 0 right := 0 zero := 0 longestSubarray := 0 n := len(nums) for right < n { if nums[right] == 0 { zero++ } if zero > 1 { left++ if nums[left-1] == 0 { zero-- } } if zero == 1 || right == n-1 { longestSubarray = max(longestSubarray, right-left+1) } right++ } return longestSubarray - 1 } func max(a, b int) int { if a > b { return a } return b }
四、复杂度分析
4.1 方法一：滑动窗口
- 时间复杂度：O(N)，因为每个元素只遍历了一次。
- 空间复杂度：O(1)，因为使用了常数个空间。
