📝个人主页：五敷有你
🔥系列专栏：算法分析与设计
⛺️稳中求进，晒太阳
题目
示例
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"
思路（滑动窗口）
滑动窗口+双指针（快慢指针）
滑动窗口算法适用于解决具有子序列或子数组的问题，其中问题的解可以通过在输入序列中移动一个窗口（子序列或子数组）来得到。一些常见的情况下可以选择滑动窗口算法包括：
- 子串或子数组问题： 当问题需要在数组或字符串中找到一个连续的子串或子数组，使得满足一些条件时，滑动窗口是一个常见的选择。
- 不含重复字符的最长子串问题： 如题目中提到的情况，需要找到一个字符串中不包含重复字符的最长子串。
- 最小覆盖子串问题： 给定一个字符串和一些字符，找到包含这些字符的最小子串。
- 找到所有字母异位词问题： 在一个字符串中找到所有长度为固定大小的字母异位词。
- 最大连续1的个数 III 问题： 在一个二进制数组中找到最大连续的1，可以进行最多k次翻转。
算法设计与分析
代码实现
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> charSet = new HashSet<>();
int start = 0, end = 0, maxLength = 0;
while (end < s.length()) {
if (!charSet.contains(s.charAt(end))) {
charSet.add(s.charAt(end));
end++;
maxLength = Math.max(maxLength, end - start);
} else {
charSet.remove(s.charAt(start));
start++;
}
}
return maxLength;
}
}运行结果
时间复杂度分析：
在这个算法中，每个字符最多被访问两次，即在 end 指针的移动过程中。start 指针和 end 指针分别向右移动，整个过程时间复杂度是 O(n)。因此，这个算法的时间复杂度是线性的，其中 n 是字符串的长度。
遍历字符串的过程只涉及两个指针的移动和哈希集合的插入、删除操作，这些操作都是 O(1) 的复杂度。因此，整体时间复杂度为 O(n)。