首页 > 代码库 > 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));    }}