首页 > 代码库 > LongestSubstringWithoutRepeatingCharacters - leetcode java
LongestSubstringWithoutRepeatingCharacters - leetcode java
维护一个窗口,每次关注窗口中的字符串,在每次判断中,左窗口和右窗口选择其一向前移动。维护一个HashSet, 正常情况下移动右窗口,如果没有出现重复则继续移动右窗口,如果发现重复字符,则说明当前窗口中的串已经不满足要求,继续移动有窗口不可能得到更好的结果,此时移动左窗口,直到不再有重复字符为止,中间跳过的这些串中不会有更好的结果,因为他们不是重复就是更短。因为左窗口和右窗口都只向前,所以两个窗口都对每个元素访问不超过一遍,因此时间复杂度为O(2*n)=O(n),是线性算法。空间复杂度为HashSet的size,也是O(n). 代码如下:
package edu.bupt.cici.leetcode;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;import java.util.Iterator;public class LongestSubstringWithoutRepeatingCharacters { public int lengthOfLongestSubstring(String s) { if (s == null && s.length() == 0) return 0; HashSet<Character> set = new HashSet<Character>(); int max = 0; int walker = 0; int runner = 0; while (runner < s.length()) { if (set.contains(s.charAt(runner))) { if (max < runner - walker) { max = runner - walker; } while (s.charAt(walker) != s.charAt(runner)) { set.remove(s.charAt(walker)); walker++; } walker++; } else { set.add(s.charAt(runner)); } runner++; } max = Math.max(max, runner - walker); return max; } public static void main(String[] args) { // TODO Auto-generated method stub LongestSubstringWithoutRepeatingCharacters sol = new LongestSubstringWithoutRepeatingCharacters(); String s = "abcaaaaabcd"; System.out.println(sol.lengthOfLongestSubstring(s)); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。