一、209.长度最小的子数组
1.1:题目
题目链接
1.2:解题思路
-
题型:滑动窗口;时间复杂度:
O(n)
🪧 滑动窗口本质也是双指针的一种技巧,特别适用于字串问题 -
❗❗核心思想/ 关键:左右指针滑窗口,一前一后齐头进。
详细思路建议看前一篇:【Leetcode每日一刷】数组|双指针篇:977. 有序数组的平方、76. 最小覆盖子串(附滑动窗口法详解) -
算法框架:注意下面框架中的6个关键点!
/* 滑动窗口算法框架 */ void slidingWindow(string s) { // ⭐1)用合适的数据结构记录窗口中的数据情况(以便和所需的可行解进行比对) unordered_map<char, int> window; // ⭐2)// 记录最小符合条件子串的起始索引及长度 int start = 0, len = INT_MAX; //根据实际算法所需答案进行调整 int left = 0, right = 0; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; window.add(c) // 增大窗口 right++; // ⭐3)进行增大窗口后,更新关于记录当前窗口内数据情况的变量(以便稍后和所需的可行解进行比对) ... /*** debug 输出的位置 ***/ // 注意在最终的解法代码中不要 print // 因为 IO 操作很耗时,可能导致超时 printf("window: [%d, %d)\n", left, right); /********************/ // ⭐4)找到可行解——判断左侧窗口是否要收缩(进行更新) while (left < right && window needs shrink) { //进入到这个while里面说明找到一个可行解 //⭐5)进行最终的所需的答案更新 // eg:在这里更新符合条件的*最小*子串(即最终结果) if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s[left]; window.remove(d) // 缩小窗口 left++; // ⭐6)进行缩小窗口后,更新关于记录当前窗口内数据情况的变量(以便稍后和所需的可行解进行比对) ... } } }
🌟1.
3)
和6)
的操作分别是扩大和缩小窗口后的更新操作,等会你会发现它们操作是完全对称的。作用都是更新当前窗口中的数据情况,再拿去和题目所需的可行解进行比对,判断当前窗口内的情况是否可行!🌟2.
5)
步也很关键,它的作用是:找到一个可行解&更新得到一个可行解后,对题目最终需要的最优答案进行更新! -
本题思路(依据算法框架):
- ⭐首先设置一个记录当前窗口情况的变量
windowSum
(作用是方便与所需可行条件进行比较)——记录当前窗口中元素综合 - ⭐设置存储最终答案(窗口长度)的变量(作用是得到可行情况后,进行实时更新,以得到最终的最优答案)
- ⭐设置
left
和right
指针对窗口大小进行控制 - ⭐在窗口的增大和缩小过程中实时更新记录当前窗口情况的变量
windowSum
- ⭐在得到可行解的情况下,实时更新最终答案
- ⭐首先设置一个记录当前窗口情况的变量
1.3:实现代码——c++
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//设置一个记录当前窗口情况的变量(即当前窗口内元素总和
int windowSum = 0;
//算法的最终答案:minLen
int minLen = INT_MAX;
int left =0, right = 0;
while(left <= right && right < nums.size()){
//先记下窗口待新增元素
int a = nums[right];
right++;
//增大窗口后,更新当前窗口中的情况
windowSum += a;
while(left <= right && windowSum >= target){
//首先,因为进入循环就代表得到哦一个可行结果,立马更新答案
minLen = min(minLen, right - left);
//先记下窗口待减少元素
int b = nums[left];
left++;
//窗口减小后,更新记录当前窗口的元素
windowSum -= b;
}
}
return minLen == INT_MAX ? 0 : minLen;
}
};