【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串

简介: 【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串

题目1:209.长度最小的子数组

思路分析:

思路1:暴力枚举 O(N2)

思路2:滑动窗口 O(N)

滑动窗口整体思路:

  1. 初始化左右指针;
  2. 进窗口:循环条件、维护信息
  3. 判断:判断是否达到条件,从而决定是否出窗口。
  4. 更新结果:这一点是就题论题,需要判断在哪里更新结果位置。

本题的具体体现:

  1. 初始化左右指针:int left = 0 , right = 0;
  2. 进窗口:条件:sum += nums[right]; 维护的信息:子数组的和sum;
  3. 判断:当前子数组是否满足题干要求(sum >= target),满足记录长度;
  4. 更新结果:对于这道题而言,我们需要的是最小长度,因此一次条件成立并不能满足,需要比对后,更新结果。判断条件为成立条件,则需要在条件循环内部更新。

通俗的来讲思路的话:从left开始寻找满足题意的该位置长度最小的子数组,满足题意就到下一个位置,继续找该位置长度最小的子数组。


注意:感觉和暴力有些像,但这里我们的右端点是不需要更新到和left相同的,因为有上一个数的基础,知道上一个子数组是刚好多了右边一位才满足题意的,我们left到第二位置后,是要检查少去第一位,是否还满足,不满足就更新右端点。找到当前位置的长度最小的子数组。满足,就代表这就是当前位置最小长度的子数组,就left更新。

代码实现:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 滑动窗口
        int n = nums.size();
        int len = 0, sum = 0;
        int left=0,right=0;
        while(right<n) 
        {
            sum += nums[right];
            while (sum >= target) 
            {
                if(len==0) 
                    len=right+left+1;
                else if (right - left + 1 < len)
                    len = right - left + 1;
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return len;
    }
};

LeetCode链接:209.长度最小的子数组


题目2:3. 无重复字符的最长子串

题目分析:

就是寻找给定字符串的子串,要求子串内部没有重复出现,题干很简单。

提示中有说明:s由英文字母、数字、符号和空格组成---->简单哈希表判断重复

思想1:暴力枚举+哈希表O(N2)

找每个位置的无重复字符的最大子串,left不变,right去找,并通过hash表判断是否符合条件,不符合条件就结束这次循环,left到下一个位置,right更新到和left相同位置,继续重复上述操作。


思想2:滑动窗口思想+哈希表O(N)


Why?为什么使用滑动窗口思想,其实就是对暴力查找的优化,暴力查找有两个缺点:

  1. left是一个位置一个位置更新的,但在实际中比如图中例子:deabcabca ,我们在第一个位置找到的最长无重复的子串是deabc,后面是因为a重复了才结束的,我们只是left到下一个位置,其实重复位置还是一样的,仍然是a,此时的长度一定是小于上一结果的长度。我们不妨直接把left移动到第一个a后面。
  2. right每次循环都需要更新为left才开始,这也是很低效的,依旧是上面的例子:第一次循环后,left直接更新到第一个a的后面,此时开始的子串为:bc,这不就是上一次循环满足条件子串的子串吗?怎么会不符合条件呢?所以不妨right就从这个位置开始寻找。

本题的具体体现:

  1. 初始化左右指针:int left = 0 , right = 0;
  2. 进窗口:hash[s[right]]++; 维护的信息:哈希表hash;
  3. 判断:当前子串不满足条件(hash[s[right]]<=1),就进入循环,完成出哈希表 hash[s[left++]]--:更新left位置到重复字符后面,这里就是更新left位置。 更新结果len=max(len,right-left+1);;
  4. 更新结果:对于这道题,只要满足题目条件,不进循环条件,就是合适的,就可以更新len值


简单哈希表模拟: 128的空间对应ASCII码,出现过的字符,就把该字符对应ASCII码记为1,没出现过记为0,当大于1时,就是重复出现。

代码实现:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]={0};  //使用数组来简单模拟哈希表
        int left=0,right=0,n=s.size();
        int len=0;
        while(right<n)
        {
            hash[s[right]]++;       //进入窗口
            while(hash[s[right]]>1) //判断
                hash[s[left++]]--;  //出窗口
            len=max(len,right-left+1); //更新结果
            right++;
        }
        return len;
    }
};

LeetCode链接:3. 无重复字符的子串

收获满满✨:

  • Why?为什么使用滑动窗口?—> 就是对暴力枚举的优化,得出的要用这种思想;
  • hash表的简单模拟实现get;

好好刷题,好好学习专业知识,但也要好好生活哦🦖~ 天天开心!🎈

相关文章
|
22天前
|
算法 搜索推荐
力扣每日一题 6/15 滑动窗口
力扣每日一题 6/15 滑动窗口
11 1
|
22天前
|
算法 测试技术 程序员
力扣经典150题第三十题:长度最小的子数组
力扣经典150题第三十题:长度最小的子数组
10 1
|
10天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
18天前
|
索引
821.字符的最短距离-力扣(LeetCode)
821.字符的最短距离-力扣(LeetCode)
9 0
|
22天前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
16 0
|
22天前
|
存储 算法 程序员
力扣经典150题第三十一题:无重复字符的最长子串
力扣经典150题第三十一题:无重复字符的最长子串
12 0
|
1月前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值