前言
最近刷到 leetCode 里面的一道算法题, 里面有涉及到 Sliding windowing 算法, 因此写一篇文章稍微总结一下
算法题介绍
没有重复字符的子字符的最大长度: 给一个字符串, 获得没有重复字符的最长子字符的长度
例子:
输入:"abcabcbb"
输出: 3
解释: 因为没有重复字符的子字符是'abc', 所以长度是 3
解法 1: 暴力解法
- public class Solution {// 时间复杂度高 O(n3)
- public int lengthOfLongestSubstring(String s) {
- int n = s.length();
- int ans = 0;
- // 遍历所有的子字符串, 记录没有重复字母的子字符串的最大的长度
- // 获取子字符串时, 使用两个标签, 分别代表子字符串的开头和结尾
- for (int i = 0; i <n; i++)
- for (int j = i + 1; j <= n; j++)
- // 当子字符串没有重复字母时, ans 记录最大的长度
- if (allUnique(s, i, j)) ans = Math.max(ans, j - i);
- return ans;
- }
- // 判断该子字符串是否有重复的字母
- public boolean allUnique(String s, int start, int end) {
- //HashSet 实现了 Set 接口, 它不允许集合中出现重复元素.
- Set<Character> set = new HashSet<>();
- for (int i = start; i <end; i++) {
- Character ch = s.charAt(i);
- if (set.contains(ch)) return false;
- set.add(ch);
- }
- return true;
- }
- }
分析
时间复杂度: O(n3).
解法 2: 滑动窗口算法
通过使用 HashSet 作为一个滑动窗口, 检查一个字符是否已经存在于现有的子字符中只需要 O(1).
滑动窗口经常作为一个抽象的概念来处理数组 / 字符串问题. 窗口代表着一组数据 / 字符串元素, 通过开头和结尾的索引来定义窗口.
- public class Solution {// 时间复杂度 O(2n)
- // 滑动窗口算法
- public int lengthOfLongestSubstring(String s) {
- int n = s.length();
- Set<Character> set = new HashSet<>();
- int ans = 0, i = 0, j = 0;
- while (i <n && j < n) {// 窗口的左边是 i, 右边是 j, 下列算法将窗口的左右移动, 截取出其中一段
- // try to extend the range [i, j]
- if (!set.contains(s.charAt(j))){// 如果 set 中不存在该字母, 就将 j+1, 相当于窗口右边向右移动一格, 左边不动
- set.add(s.charAt(j++));
- ans = Math.max(ans, j - i);// 记录目前存在过的最大的子字符长度
- }
- else {// 如果 set 中存在该字母, 则将窗口左边向右移动一格, 右边不动, 直到该窗口中不存在重复的字符
- set.remove(s.charAt(i++));
- }
- }
- return ans;
- }
- }
分析
时间复杂度: O(2n). 在最差的情况下, 每个字符将会被访问两次
解法 3: 优化的滑动窗口算法
上面的滑动窗口算法最多需要 2n 的步骤, 但这其实是能被优化为只需要 n 步. 我们可以使用 HashMap 定义字符到索引之间的映射, 然后, 当我们发现子字符串中的重复字符时, 可以直接跳过遍历过的字符了.
- public class Solution {// 时间复杂度 o(n)
- public int lengthOfLongestSubstring(String s) {
- int n = s.length(), ans = 0;
- // 使用 hashmap 记录遍历过的字符的索引, 当发现重复的字符时, 可以将窗口的左边直接跳到该重复字符的索引处
- Map<Character, Integer> map = new HashMap<>(); // current index of character
- // try to extend the range [i, j]
- for (int j = 0, i = 0; j < n; j++) {//j 负责向右边遍历, i 根据重复字符的情况进行调整
- if (map.containsKey(s.charAt(j))) {// 当发现重复的字符时, 将字符的索引与窗口的左边进行对比, 将窗口的左边直接跳到该重复字符的索引处
- i = Math.max(map.get(s.charAt(j)), i);
- }
- // 记录子字符串的最大的长度
- ans = Math.max(ans, j - i + 1);
- //map 记录第一次遍历到 key 时的索引位置, j+1, 保证 i 跳到不包含重复字母的位置
- map.put(s.charAt(j), j + 1);
- }
- return ans;
- }
- }
分析
时间复杂度: O(n)
滑动窗口算法总结
滑动窗口算法可以用以解决数组 / 字符串的子元素问题
滑动窗口算法可以将嵌套的 for 循环问题, 转换为单循环问题, 降低时间复杂度
来源: https://juejin.im/post/5c74a2e2f265da2dea053355