力扣 无重复字符的最长子串

滑动窗口，双指针移动找集合类的元素。

题目

无重复，可想到hashset集，然后由题找最长子串，说明要处理左右边界，可以用双指针，右指针一直遍历，左指针看到重复就加一，这像是一个滑动窗口。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口
        char[] ss = s.toCharArray();
        Set<Character> set = new HashSet<>();
        int res = 0;
        for(int left = 0, right = 0; right < s.length(); right++) {//右指针自增
            char ch = ss[right];//right指向的元素
            while(set.contains(ch)) {//set中有ch，则缩短左边界
                set.remove(ss[left]);//删除ch前面的元素
                left++;
            }
            set.add(ss[right]);//加入当前元素
            res = Math.max(res, right - left + 1);//当前不重复子串的长度
        }
        return res;
    }
}

但用while移除set的字符的循环显然是很影响效率的，因此改用map去记下每个字符的索引，直接进行跳转。虽然时间复杂度和空间复杂度一样，但会快一点。

时间复杂度O(n)，空间复杂度O(n)。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int max = 0, start = 0;
        for (int end = 0; end < s.length(); end++) {
            char ch = s.charAt(end);//右边界循环遍历每个字符
            if (map.containsKey(ch)){
                //若被判断的字符上一次出现的位置就在滑动窗口内则需要改变左边界，进行+1。
                start = Math.max(map.get(ch)+1,start);
            }
            max = Math.max(max,end - start + 1);//找到最长子串
            //更新 s.charAt 的位置
            map.put(ch,end);
        }
        return max;
    }
    
}

还可以对空间复杂度进行优化，用双指针遍历，即不用存了，可以把空间复杂度到O(1)。双循环显然增加了时间复杂度，但时间复杂度O(N*∣Σ∣)。不重复子串区间长度不会超过字符集的长度∣Σ∣=128，当N足够大时，时间复杂度接近O(N)。使用set时cpu占用少，时间复杂度快一些，但显著提高了I/Os。不使用set，既减少了空间占用，又减少了I/Os，提高了运行速度。运行过后发现不用set更快。

class Solution {
  public int lengthOfLongestSubstring(String s) {
    int left = 0, length = 0, max = 0;
    for(int right=0; right < s.length(); right++){
        for(int k = left; k < right; k++){
            if(s.charAt(k) == s.charAt(right)){
                left = k+1;
                length = right-left;
                break;
            }
        }
        length++;
        if(max < length) max = length;
    }
    return max;
  }
}

以上均为优质题解的筛选，可多学一些思路。

滑动窗口要注意左右指针的遍历，然后结合常用集合类去存，在做算法题时要注意复杂度的优化。