文章目录

• 😎前言
• 🍀[长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)
• • 🚩题目描述：
  • 🚩算法思路：
  • 🚩滑动窗口可以解决问题的原因？
  • 🚩代码实现：
  • 🌲[无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)
  • • 🚩题目描述：
    • 🚩算法思路：
    • 🚩代码实现：
    • 🎍[最大连续1的个数|||](https://leetcode.cn/problems/max-consecutive-ones-iii/)
    • • 🚩题目描述：
      • 🚩算法思路：
      • 🚩代码实现：
      • 🎋[将x减到0的最小操作数](https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/)
      • • 🚩题目描述：
        • 🚩算法思路：
        • 🚩算法流程：
        • 🚩代码实现：
        • ⭕总结

          😎前言

          基本概念

          滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。

          分类：窗口有两类，一种是固定大小类的窗口，一类是大小动态变化的窗口。

          🍀长度最小的子数组

          🚩题目描述：

          给定一个含有 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

            class Solution {
                public int minSubArrayLen(int target, int[] nums) {
                }
            }
            

            🚩算法思路：

            由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗⼝」的思想来解决这道题。

            让滑动窗⼝满⾜：从 i 位置开始，窗⼝内所有元素的和⼩于 target （那么当窗内元素之和第⼀次⼤于等于⽬标值的时候，就是 i 位置开始，满⾜条件的最⼩⻓度）。

            做法：将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：

            • 如果窗⼝内元素之和⼤于等于 target ：更新结果，并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）

            • 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。

              🚩滑动窗口可以解决问题的原因？

              为何滑动窗⼝可以解决问题，并且时间复杂度更低？

              • 这个窗⼝寻找的是：以当前窗⼝最左侧元素（记为 left1 ）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满⾜区间和 sum >= target 时的最右侧（记为right1 ）能到哪⾥。
              • 我们既然已经找到从 left1 开始的最优的区间，那么就可以⼤胆舍去 left1 。但是如果继续像⽅法⼀⼀样，重新开始统计第⼆个元素（ left2 ）往后的和，势必会有⼤量重复的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候⽤上的）。
              • 此时， rigth1 的作⽤就体现出来了，我们只需将 left1 这个值从sum 中剔除。从right1 这个元素开始，往后找满⾜ left2 元素的区间（此时 right1 也有可能是满⾜的，因为 left1 可能很⼩。 sum 剔除掉 left1 之后，依旧满⾜⼤于等于target ）。这样我们就能省掉⼤量重复的计算。

                这样我们不仅能解决问题，⽽且效率也会⼤⼤提升。时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是O(N)

                🚩代码实现：

                class Solution {
                    public int minSubArrayLen(int target, int[] nums)
                    {
                        int n = nums.length;
                        int sum = 0;
                        int len = Integer.MAX_VALUE;
                        for(int left = 0, right = 0; right < n; right++) {
                            sum += nums[right]; // 进窗⼝
                            // 判断
                            while(sum >= target) {
                                len = Math.min(len, right - left + 1); // 更新结果
                                sum -= nums[left++]; // 出窗⼝
                            }
                        }
                        return len == Integer.MAX_VALUE ? 0 : len;
                    }
                }
                

                🌲无重复字符的最长子串

                🚩题目描述：

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

                • 示例 1:

                  输入: s = “abcabcbb”

                  输出: 3

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

                • 示例 2:

                  输入: s = “bbbbb”

                  输出: 1

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

                • 示例 3:

                  输入: s = “pwwkew”

                  输出: 3

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

                  class Solution {
                      public int lengthOfLongestSubstring(String s) {
                      }
                  }
                  

                  🚩算法思路：

                  研究的对象依旧是⼀段连续的区间，因此继续使⽤「滑动窗⼝」思想来优化。

                  让滑动窗⼝满⾜：窗⼝内所有元素都是不重复的。

                  做法：右端元素 ch 进⼊窗⼝的时候，哈希表统计这个字符的频次：

                  • 如果这个字符出现的频次超过 1 ，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，

                    直到 ch 这个元素的频次变为 1 ，然后再更新结果。

                  • 如果没有超过 1 ，说明当前窗⼝没有重复元素，可以直接更新结果

                    🚩代码实现：

                    class Solution {
                        public int lengthOfLongestSubstring(String ss) {
                            char[] s = ss.toCharArray();
                            int[] hash = new int[128]; // ⽤数组模拟哈希表
                            int left = 0;
                            int right = 0;
                            int n = ss.length();
                            int ret = 0;
                            while(right < n) {
                                hash[s[right]]++; // 进⼊窗⼝
                                // 判断
                                while(hash[s[right]] > 1) {
                                    hash[s[left++]]--; // 出窗⼝
                                }
                                ret = Math.max(ret, right - left + 1); // 更新结果
                                right++; // 让下⼀个字符进⼊窗⼝
                            }
                            return ret;
                        }
                    }
                    

                    🎍最大连续1的个数|||

                    🚩题目描述：

                    给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

                    • 示例 1：

                      输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2

                      输出：6

                      解释：[1,1,1,0,0,1,1,1,1,1,1]

                      粗体数字从 0 翻转到 1，最长的子数组长度为 6。

                    • 示例 2：

                      输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3

                      输出：10

                      解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]

                      粗体数字从 0 翻转到 1，最长的子数组长度为 10。

                      class Solution {
                          public int longestOnes(int[] nums, int k) {
                          }
                      }
                      

                      🚩算法思路：

                      不要去想怎么翻转，不要把问题想的很复杂，这道题的结果⽆⾮就是⼀段连续的 1 中间塞了 k 个 0 嘛。

                      因此，我们可以把问题转化成：求数组中⼀段最⻓的连续区间，要求这段区间内 0 的个数不超过 k 个。

                      既然是连续区间，可以考虑使⽤「滑动窗⼝」来解决问题。

                      算法流程：

                      1. 初始化⼀个⼤⼩为 2 的数组就可以当做哈希表 hash 了；初始化⼀些变量 left = 0 ,

                         right = 0 , ret = 0 ；

                      2. 当 right ⼩于数组⼤⼩的时候，⼀直下列循环：
                      • 让当前元素进⼊窗⼝，顺便统计到哈希表中；
                      • 检查 0 的个数是否超标：

                        如果超标，依次让左侧元素滑出窗⼝，顺便更新哈希表的值，直到 0 的个数恢复正

                        常；

                        • 程序到这⾥，说明窗⼝内元素是符合要求的，更新结果；
                        • right++ ，处理下⼀个元素；
                          3. 循环结束后， ret 存的就是最终结果

                          🚩代码实现：

                          class Solution {
                              public int longestOnes(int[] nums, int k) {
                                  int ret = 0;
                                  for(int left = 0, right = 0, zero = 0; right < nums.length; right++) {
                                      if(nums[right] == 0) {
                                          zero++; // 进窗⼝
                                      }
                                      while(zero > k) {
                                          // 判断
                                          if(nums[left++] == 0) {
                                              zero--; // 出窗⼝
                                          }
                                      }
                                      ret = Math.max(ret, right - left + 1); // 更新结果
                                  }
                                  return ret;
                              }
                          }
                          

                          🎋将x减到0的最小操作数

                          🚩题目描述：

                          给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

                          如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

                          • 示例 1：

                            输入：nums = [1,1,4,2,3], x = 5

                            输出：2

                            解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

                          • 示例 2：

                            输入：nums = [5,6,7,8,9], x = 4

                            输出：-1

                          • 示例 3：

                            输入：nums = [3,2,20,1,1,3], x = 10

                            输出：5

                            解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

                            class Solution {
                                public int minOperations(int[] nums, int x) {
                                }
                            }
                            

                            🚩算法思路：

                            题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组，信息量稍微多⼀些，不易理清思路；我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组。此时，就是熟悉的「滑动窗⼝」问题了

                            🚩算法流程：

                            1. 转化问题：求 target = sum(nums) - x 。如果 target < 0 ，问题⽆解；
                            2. 初始化左右指针 left = 0 , right = 0 （滑动窗⼝区间表⽰为 [left, right) ，左右区间是否开闭很重要，必须设定与代码⼀致），记录当前滑动窗⼝内数组和的变量 sum = 0 ，记录当前满⾜条件数组的最⼤区间⻓度 maxLen = -1 ；
                            3. 当 right ⼩于等于数组⻓度时，⼀直循环：
                            • 如果 sum < target ，右移右指针，直⾄变量和⼤于等于 target ，或右指针已经移到

                              头；

                            • 如果 sum > target ，右移左指针，直⾄变量和⼩于等于 target ，或左指针已经移到

                              头；

                            • 如果经过前两步的左右移动使得 sum == target ，维护满⾜条件数组的最⼤⻓度，并

                              让下个元素进⼊窗⼝；

                              4. 循环结束后，如果 maxLen 的值有意义，则计算结果返回；否则，返回 -1 。

                              🚩代码实现：

                              class Solution {
                                  public int minOperations(int[] nums, int x) {
                                      int sum = 0;
                                      for(int a : nums) {
                                          sum += a;
                                      }
                                      int target = sum - x;
                                      // 处理细节
                                      if(target < 0) {
                                          return -1;
                                      }
                                      int ret = -1;
                                      for(int left = 0, right = 0, tmp = 0; right < nums.length; right++) {
                                          tmp += nums[right]; // 进窗⼝
                                          // 判断
                                          while(tmp > target) {
                                              tmp -= nums[left++]; // 出窗⼝
                                          }
                                          if(tmp == target){
                                              ret = Math.max(ret, right - left + 1); // 更新结果
                                          }
                                      }
                                      if(ret == -1) {
                                          return ret;
                                      } else {
                                          return nums.length - ret;
                                      }
                                  }
                              }
                              

                              ⭕总结

                              关于《【算法优选】 滑动窗口专题——壹》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！一起加油

                               
                               网络组建管理与维护  国家住建网查企业资质  web网页设计软件  创建公司网站 教程  素材网站排行榜  h5页面制作软件app