无重复字符的最长子串

图示：针对于字符串“tmmuat”，我们需要创建两个索引值都是从0开始，再创建一个HashMap用来存放s[endIndex]:index键值对

image-20210401105649901.png
图示：通过循环遍历，不断地把对应的键值对放进HashMap中 image-20210401110306959.png
图示：当遇到HashMap中已经存在的字符时，就要更新startIndex为map[m]+1，说明遇到了重复的字符了，那么就要让当前窗口的左边界向右边挪一格；并且更新HashMap中的字符索引；但是最长子串的长度不能因为窗口的变化而变小，它需要和以往的最大窗口大小比较 image-20210401110443249.png
图示：继续保持循环遍历 image-20210401111151586.png
图示：最长子串结果随着遍历的逐渐变长 image-20210401111305945.png
图示：当再次遍历到一个重复的字符时，更新startIndex时，需要比较当前窗口左边界比较大小，左边界肯定是不能往左边走的，只能向右一往无前；同时需要更新最长子串结果。 image-20210401111719834.png
最后，以上逻辑全部转换成代码，如下：

goland语言

func lengthOfLongestSubstring(s string) int {
  // 窗口左边界
    startIndex := 0
  // 存放【字符：索引值】键值对
    hashMap := make(map[byte]int)
  // 最长子串结果值
    result := 0
  // 循环遍历
    for endIndex := 0; endIndex < len(s); endIndex++ {
    // 当命中键值对中的字符时，说明遇到重复字符了
        if index, ok := hashMap[s[endIndex]]; ok {
      // 那么就要更新窗口左边界，左边界不能向左移动，只能向右一往无前
            startIndex = max(startIndex, index+1)
        }
    // 更新字符的最新索引值
        hashMap[s[endIndex]] = endIndex
    // 更新当前遇到的最长子串结果值
        result = max(result, endIndex-startIndex+1)
    }
  // 返回最终结果值
    return result
}

// 求最大值
func max(v1 int, v2 int) int {
    if v1 > v2 {
        return v1
    }
    return v2
}

java语言

public static int lengthOfLongestSubstring(String s) {
    // 定义窗口左边界
    int startIndex = 0;
    // 存放【字符：索引值】键值对
    Map<Character, Integer> hashMap = new HashMap<>();
    // 最长子串结果值
    int result = 0;
    // 循环遍历
    for (int endIndex = 0; endIndex < s.length(); endIndex++) {
        // 当命中键值对中的字符时，说明遇到重复字符了
        Integer index = hashMap.get(s.charAt(endIndex));
        if (index != null) {
            // 那么就要更新窗口左边界，左边界不能向左移动，只能向右一往无前
            startIndex = Math.max(startIndex,index+1);
        }
        // 更新字符的最新索引值
        hashMap.put(s.charAt(endIndex),endIndex);
        // 更新当前遇到的最长子串结果值
        result=Math.max(result,endIndex-startIndex+1);
    }
    // 返回最终结果值
    return result;
}

python代码

def lengthOfLongestSubstring(self, s: str) -> int:
    # 定义窗口左边界
    startIndex = 0
    # 存放【字符：索引值】键值对
    hashMap = {}
    # 最长子串结果值
    result = 0
    # 循环遍历
    for endIndex in range(len(s)):
        # 当命中键值对中的字符时，说明遇到重复字符了
        if s[endIndex] in hashMap.keys():
            # 那么就要更新窗口左边界，左边界不能向左移动，只能向右一往无前
            startIndex = max(startIndex, hashMap[s[endIndex]] + 1)
        # 更新字符的最新索引值
        hashMap[s[endIndex]] = endIndex
        # 更新当前遇到的最长子串结果值
        result = max(result, endIndex - startIndex + 1)
    # 返回最终结果值
    return result