LeetCode常见解题思路——滑动窗口

水深无声 2022-11-08 11:57 310阅读 0赞

LeetCode常见解题思路——滑动窗口

思路说明

  • 输入：一个数组或者是字符串
  • 求解问题的共性：子数组或子字符串具有某种特性的

算法思想

通过窗口来判断子数组或子字符串是否符合题目的特性，借助两个指针来控制窗口的边界。

注意点

  • 窗口的大小是可以调整的，固定还是可变取决于问题的需求
  • 维护窗口相关的状态变量，可以有效降低计算量与算法复杂度

LeetCode相关题目

无重复字符的最长字串

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

示例 1:

  1. 输入: s = "abcabcbb"
  2. 输出: 3 
  3. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

  1. 输入: s = "bbbbb"
  2. 输出: 1
  3. 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

  1. 输入: s = "pwwkew"
  2. 输出: 3
  3. 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
  4.      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

  1. 输入: s = ""
  2. 输出: 0

提示：

  1. 0 <= s.length <= 5 * 104
  2. s 由英文字母、数字、符号和空格组成

实现思路

  • 输入校验
  • 针对子串不含重复字符的特性，挑选hashSet（无序且重复）进行对子字符不重复的特性校验
  • 由于子串有字符不重复的特性，可以采用滑动窗口的方式进行实现
  • 本文的滑动窗口大致思想是：在for循环中确定左边界后while循环判断右边界的下一位字符是否满足要求，退出循环后对当前字串的长度与当前最长长度进行比较。

代码实现

  1. class Solution { 
  2.     public int lengthOfLongestSubstring(String s) { 
  3.         if(s == null||s == ""){ 
  4.             return 0;
  5.         }
  6.         HashSet<Character> hashSet = new HashSet<>();
  7.         int winEnd = -1;
  8.         int max = 0;
  9.         for (int i = 0,n = s.length();i < n ;i++){ 
  10.             if(i!=0){ 
  11.                 hashSet.remove(s.charAt(i));
  12.             }
  13.             while(winEnd+1 < n&&!hashSet.contains(s.charAt(winEnd+1))){ 
  14.                 hashSet.add(s.charAt(winEnd+1));
  15.                 winEnd++;
  16.             }
  17.             max = Math.max(max, winEnd-i+1);
  18.         }
  19.         return max;
  20.     }
  21. }

最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

  1. 输入：nums = [1,3,2,2,5,2,3,7]
  2. 输出：5
  3. 解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：

  1. 输入：nums = [1,2,3,4]
  2. 输出：2

示例 3：

  1. 输入：nums = [1,1,1,1]
  2. 输出：0

提示：

  1. 1 <= nums.length <= 2 * 104
  2. -109 <= nums[i] <= 109

实现思路

  • 由于数组的元素具有最大值与最小值差值为1的特性，所以可以用滑动窗口进行实现
  • 本文选择对数组进行排序后再做判断

  • 本文提供了两种思路

    • 第一种，对数组的i进行遍历的同时对i和j下标对应元素的差值进行判断是否需要对j往前移位，若满足插值为1时对长度进行比较刷新最大值
    • 第二种，是博主做题思考出的解决方式，在for循环中确定左边界后while循环判断右边界的下一位元素是否满足要求，退出循环后对当前字串的长度与当前最长长度进行比较。

滑动窗口代码实现

滑动窗口实现一：推荐，复杂度为O(n)

  1. class Solution { 
  2.         public int findLHS(int[] nums) { 
  3.             if (nums == null || nums.length == 0) { 
  4.                 return 0;
  5.             }
  6.             Arrays.sort(nums);
  7.             int res = 0;
  8.             int n = nums.length;
  9.             for (int i = 0, j = 0; i < n; i++) { 
  10.                 if (nums[i] - nums[j] > 1) { 
  11.                     j++;
  12.                 }
  13.                 if (nums[i] - nums[j] == 1) { 
  14.                     res = Math.max(res, i - j + 1);
  15.                 }
  16.             }
  17.             return res;
  18.         }
  19.     }

滑动窗口实现二：复杂度高，性能较差，但是容易理解,复杂度为O(n^2)

  1. public static int findLHS(int[] nums) { 
  2.     if (nums == null || nums.length == 0) { 
  3.         return 0;
  4.     }
  5.     Arrays.sort(nums);
  6.     int res = 0;
  7.     int winEnd = -1;
  8.     for (int i = 0, n = nums.length; i < n; i++) { 
  9.         while (winEnd + 1 < n && nums[winEnd + 1] - nums[i] <= 1) { 
  10.             winEnd++;
  11.         }
  12.         res = Math.max(res, winEnd - i + 1);
  13.     }
  15.     return res;
  16. }

发表评论

表情：
评论列表 （有 0 条评论，310人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode滑动窗口

    1. 无重复字符的最长子串 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。 输入: s = “abcabcbb” 输出: 3 采用滑动窗口搜

    Bertha 。Bertha 。/ 0 赞/ 374 阅读

    相关 Leetcode解题思路总结(Easy)

    近来走上了Leetcode刷题之路，不过刷题背后更重要的是思路，掌握了方法，举一反三融会贯通。故在此我总结每道题的解题思路，这篇博客只涵盖Easy模式的题目，并按照题目从简单到

    怼烎@怼烎@/ 0 赞/ 395 阅读