image.png

    • 由于要无重复字符，我们必然要想办法记录已使用的字符来确保唯一，那就自然想到两种办法解决
      • 用容器记录已使用的字符，每添加新字符时，都判断是否有重复。
      • 维持一段不重复序列，每天添加新字符，要遍历判断是否和不重复序列不同
    • 下面是使用HashMap来记录已使用的字符，Key代表字符，Value代表字符所在下标
      • 之所以这样，是可以通过下标判断它是否被抛弃了，因为重复字符会导致之前的字符失效。

    • 因此需要几个变量来维持

      • max记录最长不重复字符的长度
      • cur记录当前维持的不重复字符的长度
      • startIndex记录当前不重复字符的开始下标
      • map记录已使用的字符
        1. public int lengthOfLongestSubstring(String s) {
        2.    int max = 0, len = s.length(), cur = 0, startIndex = 0;
        3.    Map<Character, Integer> map = new HashMap<>();
        4.    for (int i = 0; i < len; i++) {
        5.        Character ch = s.charAt(i);
        6.        //这里需要判断字符是否使用和字符是否已经失效，失效字符可以重新添加到不重复字符中
        7.        if (!map.containsKey(ch) || map.get(ch) < startIndex) {
        8.            cur++;
        9.        } else {
        10.            Integer index = map.get(ch);
        11.            //更新重复字符导致的丢失后的剩余长度
        12.            cur -= (index - startIndex);
        13.            //更新不重复字符的开始下标
        14.            startIndex = index + 1;
        15.        }
        16.        max = Math.max(cur, max);
        17.        //不管是否重复，用最新值代替
        18.        map.put(ch, i);
        19.    }
        20.    return max;
        21. }

    • 需要使用左右指针维持一个不重复序列

    • 因此需要变量
      • l：左指针
      • r：右指针
      • max记录最长不重复字符的长度
        1. public int lengthOfLongestSubstring(String s) {
        2.    int l = 0, r = 1, len = s.length(), max = 0;
        3.    for (int i = 1; i < len; i++) {
        4.        char ch = s.charAt(i);
        5.        //遍历判断不重复序列中是否有该字符
        6.        for (int j = l; j < r; j++) {
        7.            //存在，则设置新的左指针
        8.            if (s.charAt(j) == ch) {
        9.                l = j + 1;
        10.                break;
        11.            }
        12.        }
        13.        r = i + 1;
        14.        max = Math.max(max, r - l);
        15.    }
        16.    //需要特殊处理一下边界问题
        17.    return max = len == 1 ? 1 : max;
        18. }