大厂裁员消息,变少了,想跳槽加薪的人,变多了...

今天看到有人分享了一个想法：大厂裁员的消息，变少了，想跳槽加薪的人，变多了。。。

是这样吗？

确实从各个渠道得知，好像是有所回归，比去年这个时候强很多。

其实从社群的讨论也能发现，讨论面试的多了起来，讨论入职的也逐渐多了起来~

今天咱们趁着这个话题，给大家分享关于在面试中，非常常见的「滑动窗口」问题。

使用leetcode中，最为经典的2个问题。

• 无重复字符的最长子串 - 中等
• 找到字符串中所有字母异位词 - 中等

感兴趣的同学，一起来看看~

无重复字符的最长子串 - 中等

3. 无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

滑动窗口是一种用来解决数组或字符串中子串问题的有效算法。它可以将问题的时间复杂度从  降低到 ，其中  是字符串或数组的长度。

详细步骤

1. 初始化：定义一个滑动窗口，初始时窗口的左边界和右边界都指向字符串的起始位置（一开始窗口大小为 0）。同时定义一个哈希表用于记录字符的出现位置。

2. 移动右边界：从左到右遍历字符串，不断移动右边界，同时更新窗口和哈希表。

• 如果当前字符在哈希表中不存在，说明当前字符是新字符，将其加入窗口并更新哈希表。
• 如果当前字符在哈希表中已经存在，说明窗口中存在重复字符，需要收缩窗口，即移动左边界到哈希表记录的重复字符的下一个位置，同时更新哈希表中重复字符的位置。

3. 更新最大长度：在移动右边界的过程中，保持记录最大的窗口长度。

4. 重复步骤2和步骤3，直到遍历完整个字符串。

下面通过示例来说明这个算法的执行过程：

对于输入字符串 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" 的异位词。

解决这个问题的一种方法是使用滑动窗口。

详细步骤

1. 初始化：定义一个滑动窗口，初始时窗口的左边界和右边界都指向字符串的起始位置，同时定义一个哈希表用于记录窗口中字符的频次。

2. 移动右边界：从左到右遍历字符串，不断移动右边界，同时更新窗口和哈希表。

• 在每一步中，将右边界的字符加入窗口并更新哈希表中该字符的频次。
• 如果当前窗口大小等于目标字符串 p 的长度，即达到了需要匹配的长度，就需要进行下一步。

3. 检查是否为异位词：在窗口达到目标长度后，需要检查窗口中的字符频次是否与目标字符串 p 的字符频次相匹配。

• 如果匹配，则记录当前窗口的起始索引。
• 然后，移动左边界，并更新哈希表中左边界字符的频次，以继续滑动窗口。

4. 重复步骤2和步骤3，直到右边界达到字符串的末尾。

这样，通过滑动窗口的方法，我们可以找到所有 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 的异位词的起始索引。

大家可以根据解释以及代码中的注释进行学习~

好了，今天的内容先这样，大家如果觉得有用，狠狠的赞起来~

有其他想看的内容，底部发消息。

我们下期再见喽~