滑动窗口（数组）

作用滑动窗口求连续满足条件的最短子数组代码模板int left 0; int right; //外层循环扩展右边界内层循环扩展左边界 for (right 0; right n; right) { //获取当前考虑的元素 while (left right check()) {//区间[left,right]不符合题意 //统计当前状态值 //左边界移动 } //加入当前元素 } //最后跳出循环再统计一次实例例一力扣第3题给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。class Solution { public int lengthOfLongestSubstring(String s) { int n s.length(); int max 0; int left 0; SetCharacter set new HashSet(); int right; for(right 0; rightn; right){ char c s.charAt(right); while(right left set.contains(c)){ if(right - left max){ max right - left; } set.remove(s.charAt(left)); left; } //加入当前元素 set.add(c); } //做循环结束后统计 if(right - left max){ max right - left; } return max; } }例二力扣第209题给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., numsr-1, numsr]并返回其长度。如果不存在符合条件的子数组返回0。import java.util.Scanner; public class sliding_window { public static void main(String[] args) { Scanner sc new Scanner(System.in); //目标值 int target sc.nextInt(); int n sc.nextInt(); //母数组 int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } int minNum minSubArrayLen(target, arr); System.out.println(总和 target 的最短子数组长度为 minNum); } public static int minSubArrayLen(int target, int[] nums) { int n nums.length; int left 0; //记录当前子数组总和 int sum 0; //记录最短子数组长度 int minNum Integer.MAX_VALUE; //记录当前子数组长度 int num 0; //使用 right 遍历 for(int right0; rightn; right){ sum nums[right]; num; while(sum target){ minNum Math.min(minNum, num); //使用 left 缩小范围 sum - nums[left]; num--; } } if(minNum Integer.MAX_VALUE){ //不存在符合条件的子数组 return 0; }else{ return minNum; } } }