Day58 | 灵神 | 滑动窗口：长度最小的子数组&&乘积小于K的子数组&&无重复字符的最长子串

209.长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

思路：

思考的关键点：固定右指针，移动左指针，而我们要做的就是找到左指针移动的条件，即在什么情况下移动左指针，而这个条件一般都在题目中。

在本题中，我们固定右端点

image-20250310182605966

以固定4，我们目前左指针l=0，指向的是2，右指针为4，指向4

我们发现这个子数组的和是大于target7的，满足了子数组和大于target的条件，子数组大小是5，那这个时候我们就可以通过移动左指针来缩小子数组的大小。我们移动左指针，l++，发现和是10，仍旧大于target，那说明我们可以继续往左移动指针来缩小子数组的大小，一直到l=2，指向1时，我们找到了子数组和仍大于等于7的最小的子数组，因为再减一位就不大于7了，就不满足条件了，所以我们更新答案，就是右指针减去左指针再加1就是这个子数组的长度，即4-2+1=3。到这里我们就找到了以4为右端点的满足条件的最小的子数组的长度为3。

那么只要从头遍历右端点，每个端点都重复这个过程，在这之间记录最小值，那么就会找到我们想要的答案。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res=INT_MAX;//最后结果
        int sum=0;//记录数组和
        int l=0;//左指针
        //i是右指针，右端点
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            //满足条件 子数组和大于target
            while(sum>=target)
            {
                int temp=i-l+1;
                //更新答案
                res=min(res,temp);
                sum-=nums[l];
                //更新左指针
                l++;
            }
        }
        //res还是初始值，说明整个数组加起来都不到target，返回0即可
        if(res==INT_MAX)
            return 0;
        return res;
    }
};

713.乘积小于K的子数组

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

思路：

和上一题思路一样，只是这道题更新答案变为在while循环外。因为上一题在while循环内是，是满足子数组和大于target这一条件的，所以在while内更新答案。而本题sum<k即在while外才是满足条件的情况，所以在while循环外更新答案。

本题的关键点，也就是左指针移动条件是子数组乘积大于K时进行移动。

另一个关键点是子数组的数量如何计算。

假设当前满足条件的子数组为[5,2,6]，那么以6为右端点(即必须包括6)有几个满足条件的数组？

[5,2,6],[2,6],[6]这三个。而我们不需要管[5],[5,2]这类的子数组，因为这类的数组在以5或者2为右端点时已经计算过一次了。

推广一下，[l,r]这个区间的子数组乘积小于k，那么[l+1,r],…..[r,r]都是小于k的，那么数量就是

r-l+1个子数组满足条件

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k<=1)
            return 0;
        int res=0;
        int l=0;
        int sum=1;
        for(int i=0;i<nums.size();i++)
        {
            sum*=nums[i];
            //更新l使得子数组满足条件
            while(sum>=k)
            {
                //res+=(i-l+1);
                sum/=nums[l];
                l++;
            }
            //结果更新是在满足题目条件时进行更新，上一道题在while内更新是因为在while内是满足条件的时候
            //这道题是while外才是符合条件的时候，所以在while外更新结果
            res+=(i-l+1);
        }
        return res;
    }
};

3.无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

思路：

和上面两道题思路相同，固定右端点，遍历右端点。只要碰到重复的字符，那么左指针就一直往右移动，直到没有重复的字符为止。

记录字符的方式：哈希表，key为字符，value为字数个数，只要不为1就说明有重复，那就左指针一直往右移动，直到没有重复的字符。

在遍历过程中记录子串的长度，碰到长度更大的子串就更新结果。

完整代码：

注释部分是笔者原来的错误，没有找到正确的记录字符的方式。仅作为一个记录，不必在意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res=0;
        unordered_map<char,int> p;
        int l=0;
        for(int i=0;i<s.size();i++)
        {
            /*if(p.find(s[i])==p.end())
            {
                p.insert({s[i],i});
                res=max(res,i-l);
            }
            else
            {
                res=max(res,i-l);
                int temp=p[s[i]]+1;
                for(int j=l;j<=p[s[i]];j++)
                    p.erase(s[j]);
                l=temp;
                p.insert({s[i],i});
            }*/
            
            //记录字符
            p[s[i]]++;
            //移动左指针
            while(p[s[i]]!=1)
            {
                p[s[l]]--;
                l++;
            }
            //更新答案
            res=max(res,i-l+1);
        }
        return res;
    }
};