首页 > 代码库 > leetcode 3. Longest Substring Without Repeating Characters
leetcode 3. Longest Substring Without Repeating Characters
本问题是求最长不重复子串。
给出一种方法：
例如：aplsdfgsjiuk，设置一个最长子串的起始位和结束位，a为起始位，b为结束位，当遍历aplsdfg时，下一位s重复，所以可以从d为起始位置在遍历。
public class Solution { public int lengthOfLongestSubstring(String s) { boolean []arr = new boolean[256]; for(int i = 0; i < 256; i++) { arr[i] = false; } int a = 0;//记录开始位置 int b = 0;//记录子串的结束位置 int maxlength = 0; while(b < s.length()) { if(!arr[s.charAt(b)]) { arr[s.charAt(b)] = true;// 访问过了 b++; } else { while(s.charAt(a) != s.charAt(b)) { arr[s.charAt(a)] = false; a++; } a++; b++; } maxlength = (maxlength > (b-a))? maxlength:(b-a); } return maxlength; }}
时间复杂度为O（n）。
leetcode 3. Longest Substring Without Repeating Characters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。