3. 无重复字符的最长子串

题解

一、滑动窗口（双指针）

public int lengthOfLongestSubstring(String s) {
    HashSet<Character> charContainer = new HashSet<>();
    int rp = 0;
    int maxSub = 0;
    int len = s.length();
    for (int i = 0; i < len; i++) {
       if (i > 0) {
          charContainer.remove(s.charAt(i - 1));
       }
       while (rp < len && !charContainer.contains(s.charAt(rp))) {
          charContainer.add(s.charAt(rp));
          rp++;
       }
       maxSub = Math.max(maxSub, rp - i);
    }

    return maxSub;
}

二、滑动窗口（双指针）优化

   public int lengthOfLongestSubstring(String s) {
        int len = s.length(); 
        if (len == 0) {
          return 0;
        }
        // 左指针，右指针
        int lp = 0, rp = 0;
        int maxSubLen = 0;
        HashSet<Character> maxSub = new HashSet<Character>();
        while(lp < len && rp < len) {
           if (maxSub.contains(s.charAt(rp))) {
              // 移除最前面的字符
              maxSub.remove(s.charAt(lp));
              // 如果存在重复，左指针右移，计算下一个最长子串
              lp++;
           } else {
               maxSub.add(s.charAt(rp));
               //如果没有重复，右指针右移一位
               rp++;
           }
           maxSubLen = Math.max(maxSubLen, rp - lp);
        }
        return maxSubLen;
    }

yifanzheng / leetcode-java

3. 无重复字符的最长子串 #4

题解