商城类网站设计制作,扬中信息港,常州市建设工程网站,美食网站设计风格1 题目描述
给定一个字符串 s , 请你找出其中不含有重复字符的 最长子串 的长度 示例 1:
**输入:** s abcabcbb
**输出:** 3
**解释:** 因为无重复字符的最长子串是 abc, 所以其长度为 3示例 2:
**输入:** s bbbbb
**输出:** 1
**解…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为字符下标 HashMapCharacter, 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;
}
