题目：longest-substring-without-repeating-characters

给定一个字符串 s ，请你找出其中不含有重复字符的最长 子串 的长度。

示例 1：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2：

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

1. 给定两个指针 left 和 right ，初始时都在 0
2. 给定一个哈希表，用来存出现过的字符以及它最后一次出现的下标位置：map(字符，下标)
3. 遍历数组，移动 right：
   • 如果 s[right] 不在哈希表里，更新 right 到 map 后直接计算 right 到 left 的长度
   • 如果 s[right] 在哈希表里，说明曾经出现过：
     • s[right] 曾经出现在 left 的左边 ？ 可忽略
     • s[right] 曾经出现在 left 的右边 ？ 需要更新 left 到曾经出现过的位置 + 1
   • 无论在不在哈希表，都需要更新 s[right] 到最新位置：map.put(c, right) 最后计算长度

Java 实现

import java.util.Arrays;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || "".equals(s)){
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int left = 0;
        for (int right = 0 ; right < s.length(); right++){
            Character c = s.charAt(right);
            if (map.containsKey(c)){
                int l = map.get(c);
                // 如果曾经出现的位置+1在 left 的右边，说明 left 要更新
                if (l+1 > left){
                    left = l+1;
                }
            }
            //  无论在不在哈希表，都更新 right 到最新位置
            map.put(c, right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}