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

前言

声明：题目来源于： 力扣

一、长度最小的子数组

题目链接：传送门

(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指针表示右边界，两个指针初始状态都指向第一个元素。

在这里插入图片描述

1. 定义一个变量sum，用于记录当前窗口内所有变量的和。 窗口：这里是指left指针与right指针之间的范围。
2. 右边界指针right向右移动，表示进窗口。 如果left+right<target,表示窗口不满足条件，需要新元素加入。

在这里插入图片描述

1. 左边界指针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,则我们需要出窗口，直到左边界缩小到，这个元素在窗口中只出现一次。

在这里插入图片描述

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

(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;
    }
};

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

在这里插入图片描述