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

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

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

#### 思路说明 ####

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

#### 算法思想 ####

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

**注意点**

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

### LeetCode相关题目 ###

#### 无重复字符的最长字串 ####

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

输入: s = ""
    输出: 0

提示：

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

**实现思路**

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

**代码实现**

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            if(s == null||s == ""){ 
                return 0;
            }
            HashSet<Character> hashSet = new HashSet<>();
            int winEnd = -1;
            int max = 0;
            for (int i = 0,n = s.length();i < n ;i++){ 
                if(i!=0){ 
                    hashSet.remove(s.charAt(i));
                }
                while(winEnd+1 < n&&!hashSet.contains(s.charAt(winEnd+1))){ 
                    hashSet.add(s.charAt(winEnd+1));
                    winEnd++;
                }
                max = Math.max(max, winEnd-i+1);
            }
            return max;
        }
    }

#### 最长和谐子序列 ####

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

**实现思路**

*  由于数组的元素具有最大值与最小值差值为1的特性，所以可以用滑动窗口进行实现
 *  本文选择对数组进行排序后再做判断
 *  本文提供了两种思路
    
     *  第一种，对数组的i进行遍历的同时对i和j下标对应元素的差值进行判断是否需要对j往前移位，若满足插值为1时对长度进行比较刷新最大值
     *  第二种，是博主做题思考出的解决方式，在for循环中确定左边界后while循环判断右边界的下一位元素是否满足要求，退出循环后对当前字串的长度与当前最长长度进行比较。

**滑动窗口代码实现**

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

class Solution { 
            public int findLHS(int[] nums) { 
                if (nums == null || nums.length == 0) { 
                    return 0;
                }
                Arrays.sort(nums);
                int res = 0;
                int n = nums.length;
                for (int i = 0, j = 0; i < n; i++) { 
                    if (nums[i] - nums[j] > 1) { 
                        j++;
                    }
                    if (nums[i] - nums[j] == 1) { 
                        res = Math.max(res, i - j + 1);
                    }
                }
                return res;
            }
        }

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

public static int findLHS(int[] nums) { 
        if (nums == null || nums.length == 0) { 
            return 0;
        }
        Arrays.sort(nums);
        int res = 0;
        int winEnd = -1;
        for (int i = 0, n = nums.length; i < n; i++) { 
            while (winEnd + 1 < n && nums[winEnd + 1] - nums[i] <= 1) { 
                winEnd++;
            }
            res = Math.max(res, winEnd - i + 1);
        }
    
        return res;
    }