今天看到有人分享了一个想法：大厂裁员的消息，变少了，想跳槽加薪的人，变多了。。。
是这样吗？
确实从各个渠道得知，好像是有所回归，比去年这个时候强很多。
其实从社群的讨论也能发现，讨论面试的多了起来，讨论入职的也逐渐多了起来~
今天咱们趁着这个话题，给大家分享关于在面试中，非常常见的「滑动窗口」问题。
使用leetcode中，最为经典的2个问题。
感兴趣的同学，一起来看看~
无重复字符的最长子串 - 中等
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
滑动窗口是一种用来解决数组或字符串中子串问题的有效算法。它可以将问题的时间复杂度从 降低到 ，其中 是字符串或数组的长度。
详细步骤
初始化：定义一个滑动窗口，初始时窗口的左边界和右边界都指向字符串的起始位置（一开始窗口大小为 0）。同时定义一个哈希表用于记录字符的出现位置。
移动右边界：从左到右遍历字符串，不断移动右边界，同时更新窗口和哈希表。
- 如果当前字符在哈希表中不存在，说明当前字符是新字符，将其加入窗口并更新哈希表。
- 如果当前字符在哈希表中已经存在，说明窗口中存在重复字符，需要收缩窗口，即移动左边界到哈希表记录的重复字符的下一个位置，同时更新哈希表中重复字符的位置。
更新最大长度：在移动右边界的过程中，保持记录最大的窗口长度。
下面通过示例来说明这个算法的执行过程：
对于输入字符串 s = "abcabcbb"：
- 移动右边界：依次遍历字符，第一个字符 'a' 加入窗口和哈希表，当前窗口为 "a"。
- 继续移动右边界：字符 'b' 加入窗口和哈希表，当前窗口为 "ab"。
- 继续移动右边界：字符 'c' 加入窗口和哈希表，当前窗口为 "abc"。
- 继续移动右边界：字符 'a' 在哈希表中已存在，窗口需要收缩，将左边界移动到哈希表记录的 'a' 的下一个位置（即原来的位置加1），此时窗口变为 "bca"。
- 继续移动右边界：字符 'b' 在哈希表中已存在，窗口需要收缩，将左边界移动到哈希表记录的 'b' 的下一个位置，此时窗口变为 "cab"。
- 继续移动右边界：字符 'b' 在哈希表中已存在，窗口需要收缩，将左边界移动到哈希表记录的 'b' 的下一个位置，此时窗口变为 "abc"。
- 继续移动右边界：字符 'b' 在哈希表中已存在，窗口需要收缩，将左边界移动到哈希表记录的 'b' 的下一个位置，此时窗口变为 "c"。
- 继续移动右边界：字符 'b' 加入窗口和哈希表，当前窗口为 "cb"。
- 继续移动右边界：字符 'b' 在哈希表中已存在，窗口需要收缩，将左边界移动到哈希表记录的 'b' 的下一个位置，此时窗口变为 "b"。
在遍历过程中，记录窗口长度的最大值为 3，因此答案是 3。
这就是使用滑动窗口算法解决这个问题的完整思路和步骤。
Python代码
def length_of_longest_substring(s: str) -> int:
# 初始化左右指针和最大长度
left = 0
max_length = 0
# 使用字典记录字符的索引位置
char_index = {}
for right in range(len(s)):
# 如果当前字符已经在窗口中出现过
if s[right] in char_index:
# 更新左指针位置，确保不会包含重复字符
left = max(left, char_index[s[right]] + 1)
# 更新当前字符的索引位置
char_index[s[right]] = right
# 更新最大长度
max_length = max(max_length, right - left + 1)
return max_length
def main():
# 测试用例
test_cases = ["abcabcbb", "bbbbb", "pwwkew"]
for s in test_cases:
print(f"Input: {s}")
print(f"Output: {length_of_longest_substring(s)}")
if __name__ == "__main__":
main()
Java代码
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringWithoutRepeatingCharacters {
public static int lengthOfLongestSubstring(String s) {
// 初始化左右指针和最大长度
int left = 0;
int maxLength = 0;
// 使用HashMap记录字符的索引位置
Map<Character, Integer> charIndex = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
// 如果当前字符已经在窗口中出现过
if (charIndex.containsKey(s.charAt(right))) {
// 更新左指针位置，确保不会包含重复字符
left = Math.max(left, charIndex.get(s.charAt(right)) + 1);
}
// 更新当前字符的索引位置
charIndex.put(s.charAt(right), right);
// 更新最大长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
// 测试用例
String[] testCases = {"abcabcbb", "bbbbb", "pwwkew"};
for (String s : testCases) {
System.out.println("Input: " + s);
System.out.println("Output: " + lengthOfLongestSubstring(s));
}
}
}
这些代码都会输出测试用例的结果以验证算法的正确性。
找到字符串中所有字母异位词 - 中等
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
解决这个问题的一种方法是使用滑动窗口。
详细步骤
初始化：定义一个滑动窗口，初始时窗口的左边界和右边界都指向字符串的起始位置，同时定义一个哈希表用于记录窗口中字符的频次。
移动右边界：从左到右遍历字符串，不断移动右边界，同时更新窗口和哈希表。
- 在每一步中，将右边界的字符加入窗口并更新哈希表中该字符的频次。
- 如果当前窗口大小等于目标字符串
p 的长度，即达到了需要匹配的长度，就需要进行下一步。
检查是否为异位词：在窗口达到目标长度后，需要检查窗口中的字符频次是否与目标字符串 p 的字符频次相匹配。
- 然后，移动左边界，并更新哈希表中左边界字符的频次，以继续滑动窗口。
这样，通过滑动窗口的方法，我们可以找到所有 p 的异位词的起始索引。
下面通过示例来说明这个算法的执行过程：
对于输入字符串 s = "cbaebabacd" 和目标字符串 p = "abc"：
- 移动右边界：依次遍历字符，第一个字符 'c' 加入窗口和哈希表，当前窗口为 "c"。
- 继续移动右边界：字符 'b' 加入窗口和哈希表，当前窗口为 "cb"。
- 继续移动右边界：字符 'a' 加入窗口和哈希表，当前窗口为 "cba"。
- 窗口大小达到目标长度，检查是否为异位词，匹配成功，记录当前窗口的起始索引 0。
- 移动左边界：将左边界字符 'c' 的频次减一，窗口变为 "ba"。
- 继续移动右边界：字符 'e' 加入窗口和哈希表，当前窗口为 "bae"。
- 继续移动右边界：字符 'b' 加入窗口和哈希表，当前窗口为 "baeb"。
- 窗口大小达到目标长度，检查是否为异位词，匹配成功，记录当前窗口的起始索引 3。
最终，得到所有 p 的异位词的起始索引 [0, 6]。
这就是使用滑动窗口算法解决这个问题的完整思路和步骤。
当使用滑动窗口算法解决这个问题时，我们可以维护一个哈希表，用于记录窗口中字符的频次。我们还需要一个计数器，用于记录当前窗口中已匹配字符的数量。
Python代码
from collections import Counter
def findAnagrams(s: str, p: str):
# 初始化窗口左右指针和计数器
left, right = 0, 0
count = len(p)
result = []
# 记录目标字符串p中每个字符的频次
p_count = Counter(p)
# 遍历字符串s
while right < len(s):
# 如果当前字符在p中出现过，则将计数器减一
if p_count[s[right]] > 0:
count -= 1
# 更新p_count中当前字符的频次
p_count[s[right]] -= 1
# 右指针右移
right += 1
# 如果当前窗口长度等于p的长度
if count == 0:
# 判断当前窗口是否为p的异位词
if right - left == len(p):
result.append(left)
# 移动左指针
if p_count[s[left]] >= 0:
count += 1
p_count[s[left]] += 1
left += 1
return result
def main():
# 测试用例
s1 = "cbaebabacd"
p1 = "abc"
print("Input:", s1, p1)
print("Output:", findAnagrams(s1, p1)) # [0, 6]
s2 = "abab"
p2 = "ab"
print("Input:", s2, p2)
print("Output:", findAnagrams(s2, p2)) # [0, 1, 2]
if __name__ == "__main__":
main()
Java代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FindAllAnagramsInAString {
public static List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
// 初始化窗口左右指针和计数器
int left = 0, right = 0, count = p.length();
// 记录目标字符串p中每个字符的频次
Map<Character, Integer> pCount = new HashMap<>();
for (char c : p.toCharArray()) {
pCount.put(c, pCount.getOrDefault(c, 0) + 1);
}
// 遍历字符串s
while (right < s.length()) {
// 如果当前字符在p中出现过，则将计数器减一
if (pCount.containsKey(s.charAt(right)) && pCount.get(s.charAt(right)) > 0) {
count--;
}
// 更新pCount中当前字符的频次
pCount.put(s.charAt(right), pCount.getOrDefault(s.charAt(right), 0) - 1);
// 右指针右移
right++;
// 如果当前窗口长度等于p的长度
if (count == 0) {
// 判断当前窗口是否为p的异位词
if (right - left == p.length()) {
result.add(left);
}
// 移动左指针
if (pCount.containsKey(s.charAt(left)) && pCount.get(s.charAt(left)) >= 0) {
count++;
}
pCount.put(s.charAt(left), pCount.getOrDefault(s.charAt(left), 0) + 1);
left++;
}
}
return result;
}
public static void main(String[] args) {
// 测试用例
String s1 = "cbaebabacd";
String p1 = "abc";
System.out.println("Input: " + s1 + ", " + p1);
System.out.println("Output: " + findAnagrams(s1, p1)); // [0, 6]
String s2 = "abab";
String p2 = "ab";
System.out.println("Input: " + s2 + ", " + p2);
System.out.println("Output: " + findAnagrams(s2, p2)); // [0, 1, 2]
}
}
这些代码实现了滑动窗口算法，用于找到字符串 s 中所有字符串 p 的异位词的起始索引。
大家可以根据解释以及代码中的注释进行学习~
好了，今天的内容先这样，大家如果觉得有用，狠狠的赞起来~
有其他想看的内容，底部发消息。
我们下期再见喽~
