算法目的
滑动窗口法，也叫尺取法（可能也不一定相等，大概就是这样 =。=），可以用来解决一些查找满足一定条件的连续区间的性质（长度等）的问题。由于区间连续，因此当区间发生变化时，可以通过旧有的计算结果对搜索空间进行剪枝，这样便减少了重复计算，降低了时间复杂度。往往类似于“请找到满足 xx 的最 x 的区间(子串、子数组)的 xx”这类问题都可以使用该方法进行解决。
大体框架
滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和窗口中的相应字符的出现次数。
例题解析
class Solution {
public: //参考TCP的滑动窗口机制，采用滑动窗口思想，固定两个点 vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> vv; int first = 1,last = 2,total = 0; while(first < last) {
//等差数列求和公式 total = (a0 + an) *n/2 total = (first + last) * (last - first + 1)/2; if(total == sum) {
vector<int> v; for(int i = first; i <= last; ++i) v.push_back(i); vv.push_back(v); ++first; } else if(total > sum) // total > sum,让first走; ++first; else //total < sum,让last走; ++last; } return vv; } }; 2.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
class Solution {
public: int minSubArrayLen(int s, vector<int>& nums) {
if(nums.size() == 0) return 0; int last = 0,_min = INT_MAX,sum = nums[0]; for(int first = 0; first < nums.size(); ++first) {
while(sum < s) //让last走 {
if(last + 1 < nums.size()) ++last; else break; sum += nums[last]; } //走到这说明sum>=s if(sum >= s) {
_min = min(_min,(last - first + 1)); } sum -= nums[first]; //first走，且让sum减去first对应的值 } if(_min == INT_MAX) return 0; return _min; } }; 3.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
class Solution {
public: int lengthOfLongestSubstring(string s) {
if(s.size() == 0 || s.size() == 1) return s.size(); int _max = 0,last = 0; //用unordered_set来记录是否出现重复 unordered_set<char> se; se.insert(s[0]); for(int first = 0;first < s.size(); ++first) {
se.insert(s[first]); if(last == first) //相等让last走一步 ++last; //如果last不越界且不重复 while(last < s.size() && se.count(s[last]) != 1) {
se.insert(s[last]); ++last; } //说明last越界或者出现重复,不管是什么情况，都要经历max比较 _max = max(last - first,_max); //删除起始元素 se.erase(s[first]); } return _max; } }; 发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/214947.html原文链接：https://javaforall.net
