基础算法之滑动窗口--Java实现(上)--LeetCode题解:长度最小的子数组-无重复字符的子串-最大连续1的个数III-将x减到0的最小操作数

这里是Thembefue

今天讲解算法中较为经典的一个算法 => 滑动窗口

本讲解主要通过题目来讲解以理解算法

讲解分为三部分：题目解析 => 算法讲解 => 编写代码

滑动窗口

在正式进入题目的讲解之前，得先了解一下什么是滑动窗口，以及应该在什么情况下使用。

滑动窗口其实是由"暴力遍历"优化来的，其本质也是双指针，但这个双指针是利用数组等单调性同向移动的，不会倒退，使其像一个窗口一个从左向右滑动。

长度最小的子数组

题目解析

找到一个子数组，使这个子数组的和大于等于给定的目标值，子数组是数组上连续的一段，一定是连续的！

算法讲解

本题使用暴力遍历的时间复杂度位O(n*2)，所以一定会超时。

所以我们在暴力遍历的基础上进行优化，根据数组的单调性，我们没必要在 left 指针向右移时，让 right 指针重新回来再遍历一次，这样会导致重复遍历，徒增时间。

滑动窗口：这个过程一般都分为四步，进窗口，判断，出窗口，更新结果。

其中更新结果可能在出窗口前，也可能在出窗口后，根据题目意思即可。

我们先维护一个 sum 变量，用于表示当前窗口中所有元素的全部和，当和大于等于 target时，我们便可更新结果，并且让此时应该让left 指向的元素出窗口。

编写代码

java">class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0, right = 0;int sum = 0, len = Integer.MAX_VALUE;while (right < nums.length) {// 进窗口sum += nums[right];// 开始缩小窗口while (sum >= target) {len = Math.min(len, right - left + 1);sum -= nums[left++]; // 出窗口} right++;}return len == Integer.MAX_VALUE ? 0 : len;}
}

无重复字符的最长子串

题目解析

子串和子数组其实就是一个意思，连续的一段子字符串，且这段字符串不能出现重复的字符，返回其最长子串。

算法讲解

本题需要借用一个数据结构来实现，也即是哈希表，哈希表记录某个字符出现的次数。

首先是进窗口操作，也就是把当前字符放入到哈希表，同时更新其出现的次数。

当出现了两次相同的字符时，说明此子串不符合条件。此时 left 指针移动，缩小窗口。

随后更新结果。

编写代码

java">class Solution {public int lengthOfLongestSubstring(String s) {int[] hash = new int[128];int left = 0, right = 0;int len = 0;while (right < s.length()) {// 进窗口hash[s.charAt(right)]++;while (hash[s.charAt(right)] > 1) {// 出窗口hash[s.charAt(left++)]--;}// 更新数据len = Math.max(len, right - left + 1);right++;}return len;}
}

最大连续1的个数 III

题目解析

同样是求符合条件的最长子数组，但其实不用真的修改数组的元素，不然要改回去就麻烦了。

算法讲解

我们可以使用一个计数器，来统计此时窗口中0出现的次数，0出现了多少次，就要将其变成1多少次。所以进出窗口的操作大差不差。

但是有一个细节，在出窗口时，0计数器不能直接减小，但 left指向的元素为0时，才能减去，否则 left一直减小，直到 0计数器减小到题目条件时。

编写代码

java">class Solution {public int longestOnes(int[] nums, int k) {int zeroCount = 0, ret = 0;int left = 0, right = 0;while (right < nums.length) {// 进窗口if (nums[right++] == 0) zeroCount++;while (zeroCount > k) {if (nums[left++] == 0) zeroCount--; // 出窗口}ret = Math.max(ret, right - left);}return ret;}
}

将 x 减到 0 的最小操作数

题目解析

选取数组最左边或者最右边的元素，从 x 中减去该元素，直到将 x 减为0为止，但得返回最小的操作次数。

注意：只能选取最左边或者最右边的元素，选过的元素从数组中删除，不能再使用。

算法讲解

这题乍一看好像并不是滑动窗口，因为一下操作左边，一下操作右边，并不能形成连续的一段。

但是看问题的角度有多种，俗话说：正难则反。假设我们现在选取了左边和右边的元素的一个，假设此时这两个数字的和正好等于 x，也就是满足题目的条件。

我们不难发现，除去这两个数字，剩下的元素其实构成了一个子数组，也就是一个窗口，且这个窗口的值等于数组所有元素的总和减去 x。

掌握了这个性质，这题就迎刃而解了。

编写代码

java">class Solution {public int minOperations(int[] nums, int x) {int left = 0, right = 0;int ret = -1;int sum = 0;for (int i: nums) sum += i;int target = sum - x, temp = 0;if (target < 0) return -1;while (right < nums.length) {// 进窗口temp += nums[right];// 判断while (temp > target) {temp -= nums[left++]; // 出窗口}if (temp == target) ret = Math.max(ret, right - left + 1);right++;}return ret == -1 ? -1 : nums.length - ret;}
}