在算法中，滑动窗口是一种处理连续子数组或子字符串的技术。它通过定义一个固定大小的窗口，使用两个指针，在数组或字符串上移动这个窗口，以便对窗口内的数据进行操作或计算。
一、Leetcode3.无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1.暴力破解
两个for循环把所有子串存入集合，最后找出所有子串中最大值。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0){
return 0;
}
char ss[] = s.toCharArray();
List<String> list = new ArrayList();
Set<String> set = new HashSet();
List<Integer> subList = new ArrayList();
for (int i = 0; i < ss.length; i++) {
outer:
for(int j = i;j<ss.length;j++){
list.add(String.valueOf(ss[j]));
set.add(String.valueOf(ss[j]));
if(list.size()>set.size()){
subList.add(list.size()-1);
list.clear();
set.clear();
break outer;
}
}
}
if(subList.size()==0){
return 1;
}
int max = subList.get(0);
for(int k = 0;k<subList.size();k++){
int cur = subList.get(k);
if(max<cur){
max = cur;
}
}
return max;
}
}
2.滑动窗口
- 存储窗口元素的集合（元素不可重复）：Set
- 两个指针 ：left左指针 right右指针
左右指针同时从下标0开始，右指针一直往右移动，每次移动到的元素存入窗口元素集合，记录当前长度和最大长度，如果当前长度比最大长度大，则更新最大长度；当遇到当前元素与窗口集合中的元素相同时，移动左指针，同时更新窗口的元素集合（窗口存储的是左右指针之间的元素），直到右指针的元素可以放入窗口集合则左指针停下来，继续移动右指针；如此反复，直到右指针遍历完所有元素，移动过程中记录的最大长度就是最长子串。
最长子串.jpeg
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray();
Set<Character> set = new HashSet<>();
int maxLength = 0;
int left = 0;
// 右指针前进
for (int right = 0; right < chars.length; right++) {
if(set.add(chars[right])){
int length = right - left + 1;
if(length > maxLength){
maxLength = length;
}
}else{
while (!set.add(chars[right])){
//移除窗口元素
set.remove(chars[left]);
//左指针前进
left++;
}
}
}
return maxLength;
}
}
二、Leetcode209.长度最小的子数组
给定一个含有 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
1.暴力破解
public int minSubArrayLen1(int target, int[] nums) {
int result = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum = sum + nums[j];
if (sum >= target) {
int length = j - i + 1;
if (result > length) {
result = length;
}
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
此种解法力扣通不过
2.前缀和+二分
这种解法是暴力的优化，在第二层for循环中 ，不是一个个的找，而是使用二分来提高查找效率，从而降低时间复杂度
public int minSubArrayLen2(int target, int[] nums) {
// 前缀和数组
int[] sums = new int[nums.length+1];
sums[0] = 0;
for (int i = 1; i <= nums.length; i++) {
sums[i] = sums[i - 1] + nums[i-1];
}
int result = Integer.MAX_VALUE;
for (int k = 0; k < sums.length; k++) {
// 二分查找
int i = k;
int j = sums.length - 1;
while (i <= j) {
int mid = (i + j) >>> 1;
if (sums[mid] - sums[k] >= target) {
j = mid - 1;
if((mid-k) < result){
result = mid-k;
}
} else {
i = mid + 1;
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
3.滑动窗口
思路：使用两个指针，左指针和右指针来固定窗口，右指针一直前进，当前进到窗口中的元素总和大于等于了目标target的时候，右指针停下来，移动左指针，看是否还有更小长度的能满足目标。不满足的时候，右指针继续前进，如此反复，找到一个最小长度的窗口元素。
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int result = Integer.MAX_VALUE;
int sum = 0;
// 右指针right前进
for (int right = 0; right < nums.length; right++) {
sum = sum + nums[right];
while (sum >= target) {
int length = right - left + 1;
if (length < result) {
result = length;
}
//更新sum
sum = sum - nums[left];
//缩小窗口 左指针前进
left++;
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
