前言
题单LeetCode 热题 100的滑动窗口部分，给出解析。
3. Longest Substring Without Repeating Characters
原题链接
题目描述
Given a string s, find the length of the longest substring without repeating characters.
Constraints:
0 <= s.length <= 5 * 10^4s consists of English letters, digits, symbols and spaces.
解题方法
这个问题可以通过「滑动窗口」技术来解决，具体到这个问题则是使用一个窗口记录子串的字符，当窗口内出现重复字符时，将窗口的左边界右移，直到没有重复的字符为止。窗口的右边界可以不断右移，同时更新最大无重复子串的长度。
算法步骤：
- 使用两个指针
left 和 right 维护滑动窗口，初始时都指向字符串的起点。
- 使用一个哈希集合
set 来记录当前窗口内的字符。
- 每次移动
right 指针，如果字符不在集合中，说明没有重复字符，将字符加入集合，同时更新最大长度。
- 如果字符已经在集合中，说明有重复字符，移动
left 指针，直到去掉重复字符。
- 继续移动
right 指针，直到遍历完整个字符串。
代码实现
Python版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if len(s) == 0:
return 0
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
|
Java版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> charSet = new HashSet<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
while (charSet.contains(s.charAt(right))) {
charSet.remove(s.charAt(left));
left++;
}
charSet.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}
|
复杂度分析
时间复杂度：$O(n)$，仅需遍历一次。
空间复杂度：$O(1)$，存储最大非重复子串的集合（字符一共26个为常数值）。
438. Find All Anagrams in a String
原题链接
题目描述
Given two strings s and p, return an array of all the start indices of p‘s anagrams in s. You may return the answer in any order .
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Constraints:
1 <= s.length, p.length <= 3 * 10^4s and p consist of lowercase English letters.
解题方法
这个问题可以通过「滑动窗口」技术来解决，具体思路是，我们维护一个长度等于字符串 p 的滑动窗口，在字符串 s 上不断移动这个窗口，并在移动过程中判断窗口内的字符串是否为字符串 p 的异位词（Anagram）。
算法步骤：
- 初始化两个计数器，一个用于字符串
p 的字母计数，另一个用于当前窗口的字母计数。
- 从
s 的起始位置开始，维护一个长度为 p 的滑动窗口，逐个字符地滑动。当窗口右移时，更新窗口中的字母计数。
- 在每次窗口移动之后，比较窗口内的字母计数和字符串
p 的字母计数。如果两个计数器相同，则记录当前窗口的起始索引。
- 返回所有符合条件的起始索引。
代码实现
Python版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
result = []
p_count = Counter(p)
s_count = Counter()
p_len = len(p)
for i in range(len(s)):
s_count[s[i]] += 1
if i >= p_len:
if s_count[s[i - p_len]] == 1:
del s_count[s[i - p_len]]
else:
s_count[s[i - p_len]] -= 1
if s_count == p_count:
result.append(i - p_len + 1)
return result
|
Java版本：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] pCount = new int[26];
int[] sCount = new int[26];
for (int i = 0; i < p.length(); i++) {
pCount[p.charAt(i) - 'a']++;
sCount[s.charAt(i) - 'a']++;
}
if (matches(pCount, sCount)) {
result.add(0);
}
for (int i = p.length(); i < s.length(); i++) {
sCount[s.charAt(i) - 'a']++;
sCount[s.charAt(i - p.length()) - 'a']--;
if (matches(pCount, sCount)) {
result.add(i - p.length() + 1);
}
}
return result;
}
private boolean matches(int[] pCount, int[] sCount) {
for (int i = 0; i < 26; i++) {
if (pCount[i] != sCount[i]) {
return false;
}
}
return true;
}
}
|
复杂度分析
时间复杂度：$O(n)$，仅需遍历一次。
空间复杂度：$O(1)$，字符一共26个为常数值。
