内容简介:最近刷到leetCode里面的一道算法题,里面有涉及到Sliding windowing算法,因此写一篇文章稍微总结一下没有重复字符的子字符的最大长度:给一个字符串,获得没有重复字符的最长子字符的长度例子:
最近刷到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; } } 复制代码
以上所述就是小编给大家介绍的《滑动窗口(Sliding Window)算法介绍》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Go实现网站访问量控制(滑动窗口算法,类似利用Redis List数据结构属性)
- 滑动验证码的原理并利用 Vue 实现滑动验证码
- Flink 滑动窗口优化
- Flink 滑动窗口优化
- Flink 滑动窗口优化
- 撸一款”灵动“的滑动按钮
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
乔布斯离开了,马斯克来了
[日]竹内一正 / 干太阳 / 中信出版社 / 2015-11
在电动汽车的创新上,特斯拉抓住了一个群体的独特需求,外形很酷,不烧油,智能化控制。所有的颠覆式创新都不是敲锣打鼓来的,而是隐藏在一片噪声里,马斯克给我们带来的特斯拉虽然不尽完美,但他做产品的思维和执着于未来的勇气,值得学习。埃隆•马斯克创办公司也不是为了赚钱,而是为了拯救人类和地球,电动汽车、太阳能发电、宇宙火箭,不管是哪一项都足以令一个国家付出巨大的代价去研究开发,但埃隆•马斯克却一个人在做这些......一起来看看 《乔布斯离开了,马斯克来了》 这本书的介绍吧!