滑动窗口

文章目录

说明解题框架例子

说明

滑动窗口算法本质就像卷尺拉伸缩短测量不断的拉伸或伸缩来获取一个满足的条件，因为每次只拉伸一格，所以可以减少窗口中的内容重复计算问题

解题框架

//左边界 int left=0; //右边界 int right=0; //窗口元素 List<E> list; while(循环条件){ if(条件1){ //目标值小于窗口和时右边界向右(右边界扩大窗口) list.add(e); j++; }else if(sum>target){ //目标值小于窗口和时左边界向右(左边界缩小窗口) list.remove(0); i++; }else{ //满足条件记录结果 //list即满足条件的结果集 //左边界向右移动继续寻找满足条件的结果集（左边界缩小窗口） sum-=i; i++; } }

例子

剑指 Offer 57 - II. 和为s的连续正数序列 https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

public int[][] findContinuousSequence(int target) { //左边界 int i=1; //右边界 int j=1; int sum = 0; List<int[]> list = new ArrayList<>(); while(i<target){ if(sum<target){ //目标值小于窗口和时右边界向右 sum+=j; j++; }else if(sum>target){ //目标值小于窗口和时左边界向右 sum-=i; i++; }else{ //满足条件记录结果 int[] tmp =new int[j-i]; for(int k=i;k<j;k++){ tmp[k-i] =k; } list.add(tmp); //左边界向右移动 sum-=i; i++; } } return list.toArray(new int[list.size()][]); }