python大型网站开发上海外贸营销网站建设

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 * 104
• s 由英文字母、数字、符号和空格组成

2 解题思路

解题思路

1. 滑动窗口 + 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;  
}