专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

据某官方媒体报道，一企业为了裁员，让人事假扮猎头诱导老员工离职，此前该公司还以业绩不达标为由将员工工资从上万元降到3000，以此来达到裁员的目的。为了裁员真的是煞费苦心，无所不用其极，从未见过如此厚颜无耻的企业。

法院判决的结果是违法解除劳动合同，估计最多也就给点赔偿，不知道会不会受到惩罚。所以如果大家没有投简历，有猎头找到你，要确认该猎头是不是公司hr，或者是公司安排的其他人员，要擦亮眼睛，辨识真伪。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1493题：删掉一个元素以后全为 1 的最长子数组，难度是中等。

给你一个二进制数组 nums ，你需要从中删掉一个元素。请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0 。

示例1：

输入：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] 。

示例2：

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

  • 1 <= nums.length <= 10^5

  • nums[i] 要么是 0 要么是 1 。

问题分析

这题说的是给定一个二进制数组，从中删除一个元素的情况下，返回最长的全为 1 的子数组长度。

这是一道典型的滑动窗口问题，滑动的时候累加窗口中元素的和sum：

1，如果窗口的长度len等于sum的值，说明窗口中的元素全部为 1 。

2，如果窗口的长度len=sum+1，说明窗口中只有 1 个 0 ，其他都是 1 。

3，如果窗口的长度len>sum+1，说明窗口中 0 的个数大于 1 ，只有这种情况下才会滑动窗口的左边界。

最后窗口的长度就是我们要求的解，这个窗口是只增不减窗口，就是窗口的大小只能增大不能减小，具体可以看下中对滑动窗口的三个总结。

JAVA：

publicintlongestSubarray(int[] nums){     int left = 0, right = 0, n = nums.length;     int sum = 0;// 窗口中元素的和     while (right < n) {         sum += nums[right];// 累加窗口中元素的和         if (sum < right - left)             sum -= nums[left++];         right++;     }     // 因为在最后right执行了加 1 ，所以窗口的     // 长度是right-left，还要减去一个删除的字符。     return right - left - 1; }

C++：

public:     intlongestSubarray(vector

 &nums){         int left = 0, right = 0, n = nums.size();         int sum = 0;// 窗口中元素的和         while (right < n) {             sum += nums[right];// 累加窗口中元素的和             if (sum < right - left)                 sum -= nums[left++];             right++;         }         // 因为在最后right执行了加 1 ，所以窗口的         // 长度是right-left，还要减去一个删除的字符。         return right - left - 1;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。