滑动窗口_⻓度最⼩的⼦数组⽆重复字符的最⻓⼦串

⻓度最⼩的⼦数组（medium

https://leetcode.cn/problems/minimum-size-subarray-sum/

思路一：两个指针，p1 p2同时指向第一个元素。sum+=p2,如果sum<target，p2++直到大于，然后记录len=right-left。p1 p2再同时指向第二个元素，再不断循环。直到p2越界。

思路2：滑动窗口

其实在思路一基础上，p2没必要再退回到p1的位置，p1++后 在原sum基础上减去p1原本指向的值，再判断sum和target大小。

这种两个 指针向同一个方向移动，p1p2的范围就像窗口一样，在数组上移动，它可以是动态的，也可以是固定的。

1.left right窗口范围

2.进窗口

3.判断

4.出窗口

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0,right=0,sum=0,len=INT_MAX;int n=nums.size();for(;right<n;right++){sum+=nums[right];//进窗口while(sum>=target)//判断{len=min(len,right-left+1);//更新结果sum-=nums[left];//出窗口left++;}}return len==INT_MAX?0:len;}
};

⽆重复字符的最⻓⼦串（medium）

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

思路：从第一个字符开始，到最后一个字符，一个一个算不重复的最长子字符串。

确实可以算但可以进行优化，

eg. de abc abcdefj  从第一个字符算 最长子字符串deabc，从第二个算eabc 第三个abc 

可以看到不重复子字符串的长度是不断变小的，因为只要子字符串中还包含a也就是重复的字符，就不可能增加。

所以用滑动窗口时，从左到右不断进窗口，等到出现重复字符时，先更新，再不断出窗口，直到把重复字符删除。

class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> charSet;int len=0;int left=0;for(int right=0;right<(int)s.size();right++){while(charSet.find(s[right])!=charSet.end())//判断{charSet.erase(s[left]);//出窗口left++;}len=max(len,right-left+1);//更新结果charSet.insert(s[right]);//入窗口}return len;}
};

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = {0}; // 使⽤数组来模拟哈希表 int left = 0, right = 0, n = s.size();int ret = 0;while (right < n) {hash[s[right]]++;          // 进⼊窗⼝while (hash[s[right]] > 1) // 判断hash[s[left++]]--;     // 出窗⼝ret = max(ret, right - left +1); // 更新结果 right++; // 让下⼀个元素进⼊窗⼝}return ret;}
};