博客
关于我
1 最长不含重复字符的子字符串
阅读量:498 次
发布时间:2019-03-07

本文共 1037 字,大约阅读时间需要 3 分钟。

为了解决这个问题,我们需要找到给定字符串中最长的不含重复字符的子串的长度。我们可以使用滑动窗口的方法来高效地解决这个问题。

方法思路

我们使用两个指针,左指针和右指针,来维护一个滑动窗口。右指针负责扩展窗口,左指针负责收缩窗口。当遇到重复字符时,左指针移动到重复字符的下一个位置,确保窗口中的字符不重复。

具体步骤如下:

  • 初始化左指针和右指针,以及一个记录最长子串长度的变量。
  • 遍历字符串,右指针从左到右移动。
  • 对于每个字符,如果字符已经在当前窗口中出现过,则移除左指针指向的字符并移动左指针。
  • 将当前字符添加到集合中,更新最长子串长度。
  • 返回最长子串的长度。
  • 解决代码

    import java.util.HashSet;import java.util.Set;public class Solution {    public int lengthOfLongestSubstring(String s) {        Set
    set = new HashSet<>(); int left = 0, max = 0; int right = 0; while (right < s.length()) { char c = s.charAt(right); while (set.contains(c)) { set.remove(s.charAt(left)); left++; } set.add(c); right++; max = Math.max(max, right - left); } return max; }}

    代码解释

  • 初始化:创建一个空集合来记录当前窗口中的字符,左指针和右指针初始化为0,max变量初始化为0。
  • 遍历字符串:右指针从字符串的开头移动到末尾。
  • 处理重复字符:当遇到重复字符时,移除左指针指向的字符并移动左指针,确保窗口中字符不重复。
  • 更新集合:将当前字符添加到集合中,记录当前窗口的长度并更新max。
  • 返回结果:遍历结束后,返回最长子串的长度。
  • 这种方法的时间复杂度为O(n),其中n是字符串的长度,能够在合理时间内处理较长的字符串。

    转载地址:http://lrwcz.baihongyu.com/

    你可能感兴趣的文章
    Python中提示:UnicodeDecodeError: 'ascii' codec can't decode byte 0xe5 in position
    查看>>
    python中数据类型存储_浅谈Python中的数据类型
    查看>>
    python中文件最重要的功能是什么-学 Python 都用来干嘛的?
    查看>>
    python中文版语言_高盛最新调查:Python超过汉语成为未来最重要技能,你准备学哪种编程语言?...
    查看>>
    Python中文问题SyntaxError
    查看>>
    Python中方括号和括号括起来的列表有什么区别?
    查看>>
    python中时间处理_Python中处理时间的几种方法小结
    查看>>
    Python中枚举串口(包括虚拟端口)的跨平台方法是什么?
    查看>>
    python中根号下a怎么写_python中根号怎么表示
    查看>>
    Python中正则表达式的巧妙使用
    查看>>
    Python中浮点数的二进制表示(位不是十六进制)
    查看>>
    Python中特殊函数和表达式 filter,map,reduce,lambda
    查看>>
    python中用socket检测端口_Python 用socket模块实现检测端口和检测web服务
    查看>>
    python中用于列表操作的plus和append有什么区别?
    查看>>
    python中用递归求和
    查看>>
    python中的@staticmethod
    查看>>
    python中的array函数作用_NumPy 数组使用大全
    查看>>
    python中的isinstance判断多个对象类型
    查看>>
    python中的keys、values、items
    查看>>
    Python中的lambda和apply结合使用
    查看>>