题目描述
输入参数
- 输入一个字符串
- 字符串的长度范围:[0,50000]
- 字符串内部的字符由英文字母、数字、符号和空格组成
题目逻辑
- 请你找出输入的字符串中不含有重复字符的最长子串的长度。
输出结果
- 最长的字符串长度值-整数（0,50000）之间
特别说明：
- 暂无
题目示例
示例 1
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc" 所以其长度为 3。 复制代码
示例 2：
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b" 所以其长度为 1。 复制代码
示例 3：
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。 复制代码
示例 4：
输入: s = "" 输出: 0 复制代码
思路分析
哈希表算法
- 定义一个哈希表存放字符及其出现的位置；
- 定义i, j分别表示不重复子串的开始位置和结束位置；
- j 向后遍历，若遇到与 [i, j] 区间内字符相同的元素，更新i的值，此时 [i, j] 区间内不存在重复字符，计算res的最大值。
AC代码
实现方法
class Solution { public int lengthOfLongestSubstring(String s) { int res = 0; Map<Character, Integer> chars = new HashMap<>(); for (int start = 0, end = 0; end < s.length(); ++end) { char c = s.charAt(end); if (chars.containsKey(c)) { // chars.get(c)+1 可能比 start 还小， // 通过 max 函数来锁住左边界 // e.g. 在"tmmzuxt"这个字符串中，遍历到最后一步时， // 最后一个字符't'和第一个字符't'是相等的。 // 如果没有 max 函数，start // 就会回到第一个't'的索引0处的下一个位置 start = Math.max(start, chars.get(c) + 1); } chars.put(c,end); res = Math.max(res, end-start + 1); } return res; } } 复制代码
总结：
- 主要是依靠于HashMap存放遍历过切不重复的字符串，key作为当前字符，value作为索引下标。
- 当于到HashMap中存在的key，这说明遇到了重复的字符，结束统计，存放到全局变量里面，进行存储长度。
- 并且进行下一步统计，根据重复元素的位置（第一个重复的元素）+1 就是重复元素的第二个的下标，进行变更开始坐标，最后进行比较最后一次收尾的长度比较。
