基础算法之滑动窗口--Java实现(上)--LeetCode题解:长度最小的子数组-无重复字符的子串-最大连续1的个数III-将x减到0的最小操作数
这里是Thembefue
今天讲解算法中较为经典的一个算法 => 滑动窗口
本讲解主要通过题目来讲解以理解算法
讲解分为三部分：题目解析 => 算法讲解 => 编写代码
滑动窗口
在正式进入题目的讲解之前，得先了解一下什么是滑动窗口，以及应该在什么情况下使用。
滑动窗口其实是由"暴力遍历"优化来的，其本质也是双指针，但这个双指针是利用数组等单调性同向移动的，不会倒退，使其像一个窗口一个从左向右滑动。
长度最小的子数组
题目解析
找到一个子数组，使这个子数组的和大于等于给定的目标值，子数组是数组上连续的一段，一定是连续的！
算法讲解
· 本题使用暴力遍历的时间复杂度位O(n*2)，所以一定会超时。
· 所以我们在暴力遍历的基础上进行优化，根据数组的单调性，我们没必要在 left 指针向右移时，让 right 指针重新回来再遍历一次，这样会导致重复遍历，徒增时间。
· 滑动窗口：这个过程一般都分为四步，进窗口，判断，出窗口，更新结果。
· 其中更新结果可能在出窗口前，也可能在出窗口后，根据题目意思即可。
· 我们先维护一个 sum 变量，用于表示当前窗口中所有元素的全部和，当和大于等于 target时，我们便可更新结果，并且让此时应该让left 指向的元素出窗口。
编写代码
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 指针移动，缩小窗口。
· 随后更新结果。
编写代码
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 计数器减小到题目条件时。
编写代码
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。
· 掌握了这个性质，这题就迎刃而解了。
编写代码
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;
}
}好了，以上就是今天内容的全部讲解，如果有不懂的地方，随时私聊😘
我们下半部分见😁
原文地址：https://blog.csdn.net/Themberfue/article/details/142679419
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！