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

#leetcode #算法/滑动窗口 #2024/07/28 #算法/双指针

目录

题目及理解

题意就是标题：删掉一个元素以后全为 1 的最长子数组

image.png

一般是删除 0 ，但有可能也需要删除 1，比如全部为 1 的场景

解题思路

使用滑动窗口技术：滑动窗口的方法非常适合解决这类“最长子数组“或“最短子数组“的问题

问题分析

  • 我们需要找到一个最长的子数组, 这个子数组最多包含一个0。
  • 删除这个0(如果存在)后，子数组应该全部由1组成。
  • 如果整个数组都是1,我们仍然需要删除一个元素。

具体思路

  • 使用两个指针 (left 和 right)来定义一个窗口，这个窗口代表我们当前考虑的子数组
    • 扩大窗口：right++
    • 缩小窗口：left++
  • 计数策略
    • 我们需要找到一个最长的子数组, 这个子数组最多包含一个0
    • 下面就是维护 0 的个数：zeroCount
  • zeroCount > 1 时，需要缩小窗口，即 left++

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
  let left = 0; // 左指针
  let right = 0; // 右指针
  let zeroCount = 0; // 0 的个数
  let res = 0; // 最长的连续的 1 的个数

  // 使用快指针，遍历数组
  for (; right < nums.length; right++) {
    
    // 如果当前元素是 0，就增加 0 的个数
    if (nums[right] === 0) {
      zeroCount++;
    }

    // 如果 0 的个数大于 1，就需要移动左指针,来减少0的数量
    // 说明窗口内 0 的数量超过了允许的最大值，这时需要收缩窗口
    while (zeroCount > 1) {
      // 如果左指针对应的元素是 0，就减少 0 的个数
      if (nums[left] === 0) {
        zeroCount--;
      }
      // 左指针右移
      left++;
    }

    // 在每次迭代中更新最大窗口长度
    res = Math.max(res, right - left + 1);
  }

  // 题目要求返回的是 1 的个数，所以需要减去 1
  // 如果整个数组都是1，我们仍然需要删除一个元素
  return res < nums.length ? res - 1 : nums.length - 1;
};

复杂度分析

  • 时间复杂度是 O(n)，其中 n 是数组的长度，因为我们只遍历数组一次。
  • 空间复杂度是 O(1)，因为我们只使用了常数级的额外空间。

错误记录

  • 边界条件处理：如果整个数组都是1，我们仍然需要删除一个元素