滑动窗口：长度最小子数组 和 无重复字符的最长字串

🎈个人主页:🎈 :???初阶牛???
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一

前言

声明：题目来源于： 力扣

一、长度最小的子数组

题目链接：传送门

(1) 题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例：

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：

子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

(2)解题思路

1. 定义两个指针，一个left，一个right。

2. left指针表示左边界，right指针表示右边界，两个指针初始状态都指向第一个元素。
   

3. 定义一个变量sum，用于记录当前窗口内所有变量的和。
   窗口：这里是指left指针与right指针之间的范围。

4. 右边界指针right向右移动，表示进窗口。
   如果left+right<target,表示窗口不满足条件，需要新元素加入。
   

5. 左边界指针left向右移动，表示出窗口。
   如果left+right>=target,表示窗口满足条件,可以统计窗口的长度，更新最短长度，需要注意的是，这里出窗口是循环的，只要窗口内元素之和sum>=target，则我们可以继续出窗口（因为我们要求最短长度）。
   

(3)代码展示:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sz=nums.size();
        int left=0,right=0;
        int sum=0,length=sz+1;
        for(left=0,right=0;right<sz;right++){
            sum+=nums[right];   //进窗口

            while(sum>=target){		//为了求最短长度，这里要循环出窗口
                length=min(length,right-left+1);	//更新最短距离
                sum-=nums[left];        //出窗口
                left++;
            }
        }
        if(length==sz+1)return 0;
        return length;

    }
};

二、无重复字符的最长字串

题目链接：传送门

(1) 题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例 1:

输入: s = "abcabcbb"
输出: 3

解释:

因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1

解释:

因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: s = "pwwkew"
输出: 3

解释:

因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

(2)解题思路

处理特殊情况：
当长度小于等于1时，返回这个字符串本身即可。

1. 定义两个指针（这里用下标充当）
   左边界指针：left
   右边界指针：right

2. 我们可以利用哈希表的特性对于每个进窗口的元素进行映射，元素进入窗口后，导致他在窗口中出现的次数>1,则我们需要出窗口，直到左边界缩小到，这个元素在窗口中只出现一次。
   

3. 每次满足要求的窗口，我们更新最长的长度即可。

(3)代码展示:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> map;
        int left = 0, right = 0;
        int sz = s.size();
        if (sz < 2)return sz;
        int max_length = 0;
        while (right < sz) {
            //进窗口
            ++map[s[right]];
            while (map[s[right]] > 1) //说明此时s[right]字符已经重复了
            {
                //left 往后走，直到这个重复元素出窗口
                --map[s[left++]];
            }
            max_length = max(max_length, right - left+1);
            right++;
        }
        return max_length;
    }
};

好了，今天的算法题就到这里了，我们下次见！