目录
- 什么时候使用不定长滑动窗口(尺取法)？
- 尺取法做法
- 跟前缀和法的区别？
- leetcode题
- 713. 乘积小于 K 的子数组
- 3. 无重复字符的最长子串
- 697. 数组的度
什么时候使用不定长滑动窗口(尺取法)？
寻找一个容器中是否有(有多少个)子容器符合某种条件，根据上述，这个条件大概率是指：小于某某值，最长不重复。可以使用尺取法。
尺取法做法
尺取法做法： 现在遇到的尺取法就是固定右边界，这时该窗口刚好符合不超过条件，当右边界往右再移动一下就会不符合条件。这时就需要右移左边界。左右指针都只会增加不会减小。
跟前缀和法的区别？
什么时候尺取法？什么时候前缀和法？那种场景下使用呢？
leetcode题
713. 乘积小于 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
- 用什么方法？为啥用这个方法？
根据题目要求关键点在于 找到子数组小于k。子数组 && 小于某某值，考虑尺取法。当从头开始，右边界一直右移，窗口积当>=k时，若右边界还是右移，则积只会越来越大，所以此时固定右边界，右移左边界，直到积 计算每个右边界对应符合条件的子数组数量：为什么是res=right-left+1而不是res=1+2+…+(right-left+1)?因为这是计算的只包含新添加进来的右边界元素的子数组，避免了与前面的重合。 例如第二次循环时 10*5
- 代码
class Solution {
public:
int numSubarrayProductLessThanK(vector& nums, int k) {
int len = nums.size();
int res = 0;
int left = 0,right = 0;
int product = 1;
for(right;right
product *= nums[right];
while(left<=right && product>k){
product /= nums[left];
++left;
}
res += right-left+1;//就算知道这个方法也想不到的地方
}
return res;
}
};
- 学到了什么？
尺取法求窗口中的子数组的个数
尺取法的思路做法
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
- 用什么方法？为啥用这个方法？
看到题目知道是找子串，可以考虑滑动窗口。
- 右指针一直往前走（窗口增长），直到添加右指针指向的元素后不符合条件（本题是有重复）
- 当右指针走到不满足条件（本题是有重复）时候需要调整左值针（也就是缩短窗口），直到再次满足条件（子串中无重复字符）
- 本题使用hash表来记录字符是否有重复。
评论中看到的方法：
每次添加一个，查看新添加元素是否与之前的字符相同，并记录长度。当相同时就标记与新添加的元素相同元素前的位置flag，下次新添加进来的元素与之前元素进行比较时就比较到flag就行，不必一直比较到0。每次新添加进来 进行比较时，len初始都为一。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
if(len == 0) return 0;
int res = 0;
unordered_map hashmap;
int left = 0;
for(int right = 0;right
++hashmap[s[right]];
while(hashmap[s[right]]>1){
--hashmap[s[left]];
++left;
}
if(right-left+1>res) res = right-left+1;
}
return res;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0;
int maxlen = 1,flag = 0;
for(int i = 1;i
int len = 1;
for(int j = i;j>flag;j--){
//这里非常重要，保证了flag指向与新添加字符相同字符前一个位置。
if(s[i]!=s[j-1]){
len++;
}else{
flag = j;
break;
}
}
maxlen = max(len,maxlen);
}
return maxlen;
}
};
- 对于寻找不重复子容器的处理不仅仅可以用滑动窗口进行调整，还可以使用新添加一个元素，让该元素与现在的子容器中元素进行对比来判断是否有重复的元素。
697. 数组的度
- 用什么方法？为啥用这个方法？
我能想到用哈希表记录下数组中每个元素的度，然后找到最大度对应的元素，并且能想到最短子数组两端一定是该元素。但是没有想到怎么解决：因为符合条件的元素可能有多个，即多个不同的数在原数组中出现次数相同
看解答后可以一个元素在和哈希表中对应一个保存三个元素数组（出现次数，第一次出现的下标，最后一次出现的下标）这样就解决了我解决不了的。 - 代码
我自己写的 通过87/89
class Solution {
public:
int findShortestSubArray(vector& nums) {
int len = nums.size();
int degree = 0;
int num;
int left = 0,right=len-1;
unordered_map hashmap;
for(int i = 0;i
++hashmap[nums[i]];
if(hashmap[nums[i]]>degree){
degree = hashmap[nums[i]];
num = nums[i];
}
}
while(nums[left]!=num) left++;
while(nums[right]!=num) right--;
return right-left+1;
}
};
改进代码
class Solution {
public:
int findShortestSubArray(vector& nums) {
int len = nums.size();
int degree = 0,minlen = 50000;
unordered_map> hashmap;
for(int i = 0;i
if(hashmap.count(nums[i])){
hashmap[nums[i]][0]++;
hashmap[nums[i]][2] = i;
}else{
hashmap[nums[i]] = {1,i,i};
}
}
for(auto [_,vec]:hashmap){
if(vec[0]>degree){
degree = vec[0];
minlen = vec[2]-vec[1]+1;
}else if(vec[0]==degree){
if(vec[2]-vec[1]+1
// if(vec[0]>=degree){
// degree = vec[0];
// if(vec[2]-vec[1]+1
// minlen = vec[2]-vec[1]+1;
// }
// }
//}
return minlen;
}
};
- 哈希表一个元素对应一个数组
- 哈希表存储顺序
