1004.最大连续1的个数III

链接：1004.最大连续1的个数III
难度：Medium
标签：数组、二分查找、前缀和、滑动窗口
简介：给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。

题解 1 - cpp

• 编辑时间：2022-01-07
• 执行用时：52ms
• 内存消耗：54.2MB
• 编程语言：cpp
• 解法介绍：滑动窗口维护窗口内 0 数。

class Solution {
   public:
    int longestOnes(vector<int>& nums, int k) {
        int ans = 0, l = 0, r = -1, cnt0 = 0;
        while (1) {
            if (cnt0 <= k) {
                r++;
                if (r == nums.size()) break;
                if (nums[r] == 0) cnt0++;
            } else {
                if (nums[l] == 0) cnt0--;
                l++;
            }
            if (cnt0 <= k) ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

题解 2 - typescript

• 编辑时间：2021-02-19
• 执行用时：112ms
• 内存消耗：44.1MB
• 编程语言：typescript
• 解法介绍：双指针。

function longestOnes(A: number[], K: number): number {
  if (A.every(v => !(v & 1))) return K;
  let l = 0;
  let r = 0;
  let sum0 = A[0] & 1 ? 0 : 1;
  let ans = sum0;
  const len = A.length;
  while (r < len) {
    if (sum0 <= K) {
      !(A[++r] & 1) && sum0++;
      ans = Math.max(ans, r - l);
    } else {
      while (sum0 > K) {
        !(A[l++] & 1) && sum0--;
      }
    }
  }
  return ans;
}