18、剑指 Offer 20. 表示数值的字符串
目录
一、题目
剑指 Offer 48. 最长不含重复字符的子字符串 难度中等
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
二、解法
2.1、滑动窗口法
核心思路：
记 left = 0 为滑动窗口的左边界下标，right = 0为右边界下标。
借助哈希表，在遍历字符串 s 时，使用哈希表 map 记录各字符最后一次出现的索引位置。
在遍历过程中，不断右移滑动窗口的右下标 right，借助 map 判断 s[right] 字符是否已经遍历过。
根据 s[right] 是否为第一次出现，有以下 2 种情况：
- 是：则 map 中不存在
key = s[right]，此时无需更新左边界 left； - 否：则 map 中存在
key = s[right]，取 value ，得到s[right]末次出现的下标，记为 index 。更新左边界 left = Math.max ( index + 1, left ) ；
更新 s[right] 末次出现的下标，记录滑动窗口的长度最大值 right - left + 1 即可。
复杂度分析
时间复杂度：O(N)
空间复杂度：O(1)，字符的 ASCII 码范围为 00 ~ 127 ，哈希表 map 最多使用 O(128) = O(1) 大小的额外空间。
Code
class Solution {
public int lengthOfLongestSubstring(String s) {
// 遍历字符串 s 时，使用哈希表 map 统计各字符最后一次出现的索引位置
HashMap<Character, Integer> map = new HashMap();
// left = 滑动窗口的左边界: result = 滑动窗口长度的最大值
int left = 0, result = 0;
// 遍历字符串 s
for (int right = 0; right < s.length(); right++) {
// 当前字符
char c = s.charAt(right);
// 如果 map 中存在 key = 当前字符
if (map.containsKey(c)) {
// 更新滑动窗口的左边界
// 左边界只允许向右移
left = Math.max(map.get(c) + 1, left);
}
// 更新当前字符末次出现的下标
map.put(s.charAt(right), right);
// 记录滑动窗口的长度最大值
result = Math.max(result, right - left + 1);
}
return result;
}
}