红动中国素材网免费下载优化营商环境条例解读
1 题目描述
给定一个字符串 s , 请你找出其中不含有重复字符的 最长子串 的长度
示例 1:
**输入:** s = "abcabcbb"
**输出:** 3
**解释:** 因为无重复字符的最长子串是 `"abc"`, 所以其长度为 3
示例 2:
**输入:** s = "bbbbb"
**输出:** 1
**解释:** 因为无重复字符的最长子串是 `"b"`, 所以其长度为 1
示例 3:
**输入:** s = "pwwkew"
**输出:** 3
**解释:** 因为无重复字符的最长子串是 `"wke"`, 所以其长度为 3请注意, 你的答案必须是 **子串** 的长度, `"pwke"` 是一个_子序列, _不是子串
提示：
0 <= s.length <= 5 * 104s由英文字母、数字、符号和空格组成
2 解题思路
解题思路
- 滑动窗口 + map, 对字符遍历一次就能找到最长子字符串, 时间复杂度 O(n)
2.1 代码实现
public int lengthOfLongestSubstring(String s) { if (null == s || s.isEmpty()) { return 0; } // key为字符串中的字符，value为字符下标 HashMap<Character, Integer> map = new HashMap<>(); // i为左指针，j为右指针 int i = -1; // res为最长子串的长度 int res = 0; for(int j = 0; j < s.length(); j++) { // 如果map中包含当前字符，则将左指针移动到当前字符的下标 if (map.containsKey(s.charAt(j))) { i = Math.max(i, map.get(s.charAt(j))); } // 将当前字符放入map中 map.put(s.charAt(j), j); // 计算最长子串的长度 res = Math.max(res, j - i); } return res;
}