LeetCode hot 100 每日一题(7)--3. 无重复字符的最长子串

这是一道难度为中等的与滑动窗口相关的题目，让我们来看看题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个_子序列，_不是子串。

提示：

0 <= s.length <= 5 * $10^4$
s 由英文字母、数字、符号和空格组成

滑动窗口是什么？

滑动窗口可以归为快慢双指针，一快一慢两个指针前后相随，中间的部分就是窗口。滑动窗口算法技巧主要用来解决子数组问题，比如让你寻找符合某个条件的最长/最短子数组。

这道题目说人话版本：

不含重复字符的子串：在这个连续的片段中，每个字符只出现一次。
子串：是指一个字符串中的连续一段字符。
在所有满足“不含重复字符”的子串中，找出那个字符个数最多的子串，并返回这个子串的长度。

题解

class Solution {public int lengthOfLongestSubstring(String s) {// 定义一个 HashMap 用于记录当前窗口中每个字符出现的次数Map<Character, Integer> window = new HashMap<>();// 初始化滑动窗口的左右指针和结果变量，left 表示窗口左边界，right 表示窗口右边界，res 用于存储最长子串的长度int left = 0;int right = 0;int res = 0;// 当右指针未达到字符串末尾时，循环遍历字符串while (right < s.length()) {// 取出右指针位置的字符，并命名为 cchar c = s.charAt(right);// 右指针右移一位，窗口扩张right++;// 将字符 c 添加到窗口中，更新其出现次数（若不存在则默认为 0，再加 1）window.put(c, window.getOrDefault(c, 0) + 1);// 如果字符 c 在窗口中的出现次数大于 1，说明窗口中存在重复字符while (window.get(c) > 1) {// 取出左指针位置的字符，记为 dchar d = s.charAt(left);// 左指针右移一位，窗口缩小left++;// 更新字符 d 在窗口中的出现次数（减去 1，因为 d 已从窗口中移除）window.put(d, window.get(d) - 1);}// 窗口内没有重复字符时，更新最长子串的长度，取当前窗口大小 (right - left) 与之前记录的最大值的较大者res = Math.max(res, right - left);}// 返回最长无重复字符子串的长度return res;}
}

问题与解答

[NOTE] 问题1
getOrDefault()的用法？
getOrDefault 是 Java 中 Map 接口提供的一个方法，用于在获取指定 key 对应的值时，如果该 key 不存在于 Map 中，则返回一个默认值，而不是返回 null。这样可以简化代码，避免额外的 null 判断。
语法：
getOrDefault(Object key, V defaultValue)
key：要查找的键。
defaultValue：当 key 不存在时返回的默认值。
例如：
Map<String, Integer> map = new HashMap<>();
map.put("apple", 2);// 获取键 "apple" 对应的值，如果不存在则返回默认值 0
int countApple = map.getOrDefault("apple", 0);  // 返回 2，因为 "apple" 存在且其值为 2// 获取键 "banana" 对应的值，如果不存在则返回默认值 0
int countBanana = map.getOrDefault("banana", 0);  // 返回 0，因为 "banana" 不存在

[NOTE] 问题2：
charAt()的用法？
charAt() 是 Java 中 String 类提供的一个方法，用于返回字符串中指定索引位置处的字符。索引从 0 开始。
例如：
String str = "Hello, World!";
char ch = str.charAt(7); // 获取索引为 7 的字符，即 'W'(前面有一个空格)
System.out.println(ch);  // 输出: W

总结

这道题目不算是一道难题。
滑动窗口算法的核心逻辑是：两个while

int left = 0, right = 0;while (right < nums.size()) {// 增大窗口window.addLast(nums[right]);right++;while (window needs shrink) {// 缩小窗口window.removeFirst(nums[left]);left++;}
}

一般的滑动窗口的题目模板如下：

// 滑动窗口算法伪码框架
void slidingWindow(String s) {// 用合适的数据结构记录窗口中的数据，根据具体场景变通// 比如说，我想记录窗口中元素出现的次数，就用 map// 如果我想记录窗口中的元素和，就可以只用一个 intObject window = ...int left = 0, right = 0;while (right < s.length()) {// c 是将移入窗口的字符char c = s[right];window.add(c)// 增大窗口right++;// 进行窗口内数据的一系列更新...// *** debug 输出的位置 ***// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时，可能导致超时printf("window: [%d, %d)\n", left, right);// ***********************// 判断左侧窗口是否要收缩while (left < right && window needs shrink) {// d 是将移出窗口的字符char d = s[left];window.remove(d)// 缩小窗口left++;// 进行窗口内数据的一系列更新...}}
}