最小滑窗模板:给定数组 nums,定义滑窗的左右边界 i, j,求满足某个条件的滑窗的最小长度。
while j < len(nums): 判断[i, j]是否满足条件 while 满足条件: 不断更新后果(留神在while内更新!) i += 1 (最大水平的压缩i,使得滑窗尽可能的小) j += 1
//209. 长度最小的子数组 int minSubArrayLen(int target, vector<int>& nums) { int left = 0, right = 0; int res = INT_MAX; int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; // 留神这里应用while,每次更新 i(起始地位),并一直比拟子序列是否符合条件 while (sum >= target) { int subLength = (i - left + 1); // 取子序列的长度 res = res < subLength ? res : subLength; if (res == 1 && sum == target) { return res; } sum -= nums[left++]; // 这里体现出滑动窗口的精华之处,一直变更i(子序列的起始地位) } } // 如果result没有被赋值的话,就返回0,阐明没有符合条件的子序列 return res == INT32_MAX ? 0 : res; }
最大滑窗模板:给定数组 nums,定义滑窗的左右边界 i, j,求满足某个条件的滑窗的最大长度。
while j < len(nums): 判断[i, j]是否满足条件 while 不满足条件: i += 1 (最激进的压缩i,一旦满足条件了就退出压缩i的过程,使得滑窗尽可能的大) 不断更新后果(留神在while外更新!) j += 1
//904. 水果成篮 int totalFruit(vector<int>& fruits) { //滑动窗口法 int left = 0; //滑动窗口左边界 int sub_len = 0; //子序列长度 int fruit_counter = 0; //篮子中的水果品种数 int len = fruits.size(); unordered_map<int, int> basket; //创立篮子 for (int j = 0; j < len; j++) { if (basket[fruits[j]] == 0) //以后水果数量在篮子中数量为零 { fruit_counter++; } basket[fruits[j]]++; while (fruit_counter > 2)//如果篮子中的水果数目超过两种,则须要挪动左边界 { basket[fruits[left]]--; //若对应水果key的value变为0,阐明篮子里曾经没有这种水果了,水果品种要对应变动(留神basket[fruits[left]] == 0即右边的水果数量为0) if (basket[fruits[left]] == 0) { fruit_counter--; } left++; } sub_len = max(sub_len, j - left + 1); } return sub_len; }
最大滑窗是在迭代右移右边界的过程中更新后果,而最小滑窗是在迭代右移左边界的过程中更新后果