3. 无重复字符的最长子串
2021/11/24 23:18:43
本文主要是介绍3. 无重复字符的最长子串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
可变字符串法
class Solution { public int lengthOfLongestSubstring(String s) { /** * 使用可变字符串 * 为了方便对子串进行增删,创建一个StringBuilder对象 * 但同时为了利用String类的indexOf()方法判断子串中是否包含重复的元素,在每次循环前将其再转换为字符串 */ int right = 0; StringBuilder str = new StringBuilder(); int max = 0; while (right < s.length()){ String temp = str.toString(); if (temp.indexOf(s.charAt(right)) < 0){ str.append(s.charAt(right)); max = Math.max(str.length(), max); right++; } /** * 如果出现了重复元素,删除子串的第一个字符再去判断 */ else { str.deleteCharAt(0); } } return max; } } /** * 时间复杂度 O(n) * 空间复杂度 O(1) */
优化1——减少排除重复元素区间的次数
class Solution { public int lengthOfLongestSubstring(String s) { /** * 使用可变字符串 * 为了方便对子串进行增删,创建一个StringBuilder对象 * 但同时为了利用String类的indexOf()方法判断子串中是否包含重复的元素,在每次循环前将其再转换为字符串 */ int right = 0; StringBuilder str = new StringBuilder(); int max = 0; while (right < s.length()){ String temp = str.toString(); int flag = temp.indexOf(s.charAt(right)); if (flag < 0){ str.append(s.charAt(right)); max = Math.max(str.length(), max); right++; } /** * 如果出现了重复元素,用flag记录下重复的位置,一次性删去该重复元素之前的所有元素 */ else { str.delete(0, flag + 1); } } return max; } } /** * 时间复杂度 O(n) * 空间复杂度 O(1) */
滑动窗口
class Solution { public int lengthOfLongestSubstring(String s) { /** * 滑动窗口 * 由于字符串的长度可能为0,因此right初始值为-1 * 因为每个字符等同于其ASCII码对应的整型,所以可以定义一个256的数组来存储每个字符出现的次数 */ int left = 0; int right = -1; int[] count = new int[256]; int max = 0; while (left < s.length()){ /** * 因为right从-1开始,因此作为索引时要加1 * 如果right + 1没有越界且当前元素没有重复,right就往后移动 * 否则让left的元素次数减1,并且left右移,直到将那个重复元素排除出当前区间 */ if (right + 1 < s.length() && count[s.charAt(right + 1)] == 0){ right++; count[s.charAt(right)]++; } else { count[s.charAt(left)]--; left++; } max = Math.max(max, right - left + 1); } return max; } } /** * 时间复杂度 O(n) * 空间复杂度 O(1) */
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
这篇关于3. 无重复字符的最长子串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-29P标签教程:初学者必备指南
- 2024-09-29PS网页切图教程:新手必学的网页设计技巧
- 2024-09-29简单易懂的Web布局教程
- 2024-09-29Web网页开发教程:从零开始的简单入门指南
- 2024-09-298D项目实战:新手入门教程
- 2024-09-29变形项目实战:新手必备入门指南
- 2024-09-29弹性盒子布局项目实战:从入门到上手
- 2024-09-29点击加载项目实战:新手入门必读教程
- 2024-09-29电商网页开发项目实战:新手入门教程
- 2024-09-29封装项目实战:从入门到初级应用