【无重复字符的最长子串--三种方法】

目录：

• 前言
• 一、题目 --无重复字符的最长子串
• • （一）双层循环
  • • 1.题目分析
    • 2.图解
    • 3.示例
    • （二）滑动窗口
    • • 1.题目分析
      • 2.图解
      • 3.示例
      • （三）滑动窗口--改进
      • • 1.题目分析
        • 2.图解
        • 3.示例
        • 二、题目--长度最小的子数组
        • • （一）滑动窗口
          • • 1.题目解析
            • 2.图解
            • 3.示例
            • ���结

              前言

              大家好，今天我们来讨论一下LeetCode上两道数组方面的例题来为大家讲解滑动窗口的使用。

              题目不难，方法很多。熊猫希望通过第一道简单的题目来使大家了解到不同的解题方法。

              ---

              一、题目 --无重复字符的最长子串

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

              点击跳转

              ---

              （一）双层循环

              1.题目分析

              题目要求找出不含重复字符的最长子串，那么我的第一想法可能就是暴力求解：

              我们需要两层循环，第一层循环遍历字符串、并且记录第二层循环开始的位置。

              ①创建一个新的数组；

              ②从第一个字符开始遍历，不重复的字符就将它放到新的数组中，遇到重复的就停止，计算该子串的长度；

              ③开始下一次循环，直到遍历到字符串结束。

              那么下面我们就来实现一下这个操作。

              在写力扣题的时候我们一定要判断空指针的情况！！

              2.图解

              3.示例

               int lengthOfLongestSubstring(char* s) { if (s == NULL) // 判断空指针 return 0; int len = strlen(s); int maxlength = 0; // 记录最长长度 int i = 0; for (i = 0; i    
              运行实例：
                
              （二）滑动窗口
               
              1.题目分析
                 
              通过上面的示例我们已经解决了问题，但是有一个问题：上面的解法时间复杂度很高：O(n^2)，
              通过画图我们可以发现内循环每进行一次都会有数据被重复移动，这个操作消耗了大量的时间，
              下面我们通过滑动窗口的方法来进行化简。
                
              2.图解
                 
              静态图：
                  
              动图：
              注：动图表示的是tmp数组中应该存放的数据
                      
              滑动窗口
                    
              3.示例
                 
              示例：
                
              int lengthOfLongestSubstring(char* s) {if (s == NULL)return 0;int len = strlen(s);char* tmp = (char*)calloc(len, 1);int right = 0; // 有效字符串长度int maxlength = 0; // 记录最长长度int i = 0;for (i = 0; i    
              运行实例：
              ![在这里插入图片描述]直https://接上传(blog.csdnimg.c-/fd4nUsR5cd89ed1e4b4085e4047a09c1b891.png)https:/
                
              （三）滑动窗口–改进
               
              1.题目分析
                 
              上面我们通过字符的复制和删除来省略了多次遍历的过程，不过，
              我们在删除字符的时候需要将后面全部的字符都往前移，这样也需要浪费一些时间，
              那么我们是否可以通过找到最长子串的具体位置，来省去删除字符的过程呢？
              答案肯定是可以的，下面就让我们开始实际操作。
                
              2.图解
                
              3.示例
                 
              示例：
                
              int lengthOfLongestSubstring(char* s) {if (s == NULL)return 0;int len = strlen(s);char* tmp = (char*)calloc(len, 1);int right = 0; // 当前字符串长度int left = 0; // 控制子串起始位置int maxlength = 0; // 记录最长长度for (int i = 0; i    
              运行实例：
                
              二、题目–长度最小的子数组
               
              题目描述：给定一个含有 n 个正整数的数组和一个正整数 target 。
              找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
               
              点击跳转
               
              （一）滑动窗口
               
              1.题目解析
                 
              题目要求找一段连续子数组，并且该子数组的和sum要>=target，那么我们首先就是要遍历数组求和，直到sum>=target，
              下面我们直接使用滑动窗口的思想进行破题： 那么我们在这里会遇到哪些特殊情况呢？
              特例1.整个数组的和都小于target，不过当窗口的右边界越界的时候我们已经跳出循环了，所以也就不需要再做特殊处理；
              特例2.有一个数组元素特别大，我们减去前面的一个元素后，sum依然大于target，这时我们就需要先将sum的值不断减小之后才能继续扩大右边界。
                
              2.图解
                    
              滑动窗口2
                      
              滑动窗口3
                 
              3.示例
                 
              代码如下：
                
              int minSubArrayLen(int target, int* nums, int numsSize){    int minlen=numsSize+1; // 最短长度    int sum=0; // 求和    int left=0; // 记录左边界    int right = 0;    while(right        sum+=nums[right++]; // 这里需要更新right，否则结果会少一        while(sum=target)  // 特例1        {            minlen = minlen>right-left?right-left:minlen;            sum-=nums[left++]; // 左下标需要右移        }    }    return minlen==numsSize+1?0:minlen; // 特例2}
                 
              运行实例：
                
              总结
               
              有些过程看似不必要，不过却可以拓宽我们的思路，拓展我们的视野。如果有什么疑问或者建议都可以在评论区留言，感谢大家对的支持。