[滑动窗口] 长度最小的子数组, 无重复字符的最长子串, 最大连续1的个数③
目录
一. LCR 008. 长度最小的子数组 - 力扣（LeetCode）
二. 3. 无重复字符的最长子串 - 力扣（LeetCode）
三. 1004. 最大连续1的个数 III - 力扣（LeetCode）
一. LCR 008. 长度最小的子数组 - 力扣（LeetCode）
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
public int minSubArrayLen(int target, int[] nums) {
// 滑动窗口 单调性
int n = nums.length;
int left = 0, right = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
while (right < n) {
sum += nums[right]; // 进窗口
while (sum >= target) { // 此时left right区间内的数的和 >= target, right没有必要继续向后走了
sum -= nums[left]; // 出窗口, right没有必要走了, 就让left走, 不断逼近target和最小长度
minLen = Math.min(right - left + 1, minLen); // 维护最小长度
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}二. 3. 无重复字符的最长子串 - 力扣（LeetCode）
给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串
的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int left = 0, right = 0;
int maxLen = 0;
int[] map = new int[128]; // 统计区间内字符的出现次数
while (right < n) {
map[s.charAt(right)]++; // 进窗口
while (map[s.charAt(right)] > 1) { // left right区间内存在重复字符, 此时移动right没有任何意义, 只能通过移动left来去除区间内的重复字符
map[s.charAt(left)]--; // 出窗口
left++;
}
maxLen = Math.max(right - left + 1, maxLen); // 维护最长子串的长度
right++;
}
return maxLen;
}三. 1004. 最大连续1的个数 III - 力扣（LeetCode）
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
public int longestOnes(int[] nums, int k) {
// 滑动窗口 问题转换成 left right区间内 0的个数 <= k
int n = nums.length;
int left = 0, right = 0;
int cnt0 = 0; // 统计0的个数
int maxLen = 0;
while (right < n) {
if (nums[right] == 0) cnt0++;
while (cnt0 > k) { // 此时left right区间内0的个数 > k, 就需要移动left来使区间内0的个数保持正常
if (nums[left] == 0) cnt0--;
left++; // 出窗口
}
maxLen = Math.max(right - left + 1, maxLen);
right++; // 进窗口
}
return maxLen;
}