IT面试题|麻瓜面试

Appearance

滑动窗口 ​

滑动窗口是双指针技巧的一种高级应用，特别适合解决子数组/子字符串的最值问题。其核心思想是维护一个窗口，通过左右指针的移动来调整窗口大小，在满足条件的过程中记录最优解。本模块涵盖无重复字符的最长子串、最小覆盖子串等经典题型，掌握窗口的扩大与收缩时机是解题关键。

Q1: 长度最小的子数组 「🟡 中级」 ​

题目描述：给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

考察点：滑动窗口、前缀和+二分查找、最短子数组。

解题思路：

  • 方法1：暴力枚举（时间O(n²)，空间O(1)）
  • 方法2：前缀和 + 二分查找（时间O(nlogn)，空间O(n)）
  • 方法3：滑动窗口，因为都是正数，窗口和单调变化（时间O(n)，空间O(1)）- 最优解

代码实现：

java
public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

复杂度分析：时间复杂度 O(n)，左右指针各移动n次；空间复杂度 O(1)。

变体扩展：

  • 变体1：和为K的子数组（有负数，不能用滑动窗口）
  • 变体2：乘积小于K的子数组
  • 变体3：最大子数组和
  • 变体4：最长湍流子数组

Q2: 无重复字符的最长子串 「🟡 中级」 ​

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

考察点：滑动窗口、哈希表/数组计数、最长子串。

解题思路：

  • 方法1：暴力枚举（时间O(n²)，空间O(1)）
  • 方法2：滑动窗口 + 哈希集合（时间O(n)，空间O(min(m, n))，m为字符集大小）- 最优解
  • 方法3：滑动窗口 + 哈希表优化，直接记录字符最新位置

代码实现：

java
public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0;
    int maxLen = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (set.contains(c)) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(c);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

复杂度分析：时间复杂度 O(n)，左右指针各移动n次；空间复杂度 O(min(m, n))，m为字符集大小。

变体扩展：

  • 变体1：至多包含两个不同字符的最长子串
  • 变体2：至多包含K个不同字符的最长子串
  • 变体3：最小覆盖子串
  • 变体4：找到字符串中所有字母异位词

Q3: 最小覆盖子串 「🔴 高级」 ​

题目描述：给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 ""。

考察点：滑动窗口进阶、最小窗口、need/window计数。

解题思路：

  • 方法：滑动窗口，右指针扩大窗口直到满足条件，左指针收缩窗口求最小值（时间O(m+n)，空间O(m)，m为t的字符种类）- 最优解

代码实现：

java
public String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, valid = 0;
    int start = 0, minLen = Integer.MAX_VALUE;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        // 满足条件时收缩窗口
        while (valid == need.size()) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            char d = s.charAt(left);
            left++;
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

复杂度分析：时间复杂度 O(m+n)，左右指针各遍历s一次；空间复杂度 O(m)，m为t中不同字符的数量。

变体扩展：

  • 变体1：无重复字符的最长子串
  • 变体2：找到字符串中所有字母异位词
  • 变体3：字符串的排列
  • 变体4：最小窗口子序列

Q4: 找到字符串中所有字母异位词 「🟡 中级」 ​

题目描述：给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

考察点：滑动窗口、固定窗口大小、字母计数数组。

解题思路：

  • 方法：滑动窗口 + 数组计数，窗口大小固定为p的长度（时间O(m+n)，空间O(1)因为字符集有限）- 最优解

代码实现：

java
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length()) return res;
    int[] need = new int[26];
    int[] window = new int[26];
    for (char c : p.toCharArray()) {
        need[c - 'a']++;
    }
    int left = 0, valid = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window[c - 'a']++;
        if (window[c - 'a'] == need[c - 'a']) {
            valid++;
        }
        // 窗口超过p长度时收缩
        while (right - left + 1 >= p.length()) {
            if (valid == countDiff(need)) {
                res.add(left);
            }
            char d = s.charAt(left);
            if (window[d - 'a'] == need[d - 'a']) {
                valid--;
            }
            window[d - 'a']--;
            left++;
        }
    }
    return res;
}

private int countDiff(int[] need) {
    int count = 0;
    for (int n : need) if (n > 0) count++;
    return count;
}

复杂度分析：时间复杂度 O(m+n)；空间复杂度 O(1)，字符集大小固定为26。

变体扩展：

  • 变体1：有效的字母异位词
  • 变体2：字符串的排列
  • 变体3：最小覆盖子串
  • 变体4：字母异位词分组

Q5: 滑动窗口最大值 「🔴 高级」 ​

题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

考察点：单调队列、滑动窗口、双向队列。

解题思路：

  • 方法1：暴力解法（时间O(nk)，空间O(1)）
  • 方法2：优先队列（大顶堆）（时间O(nlogk)，空间O(k)）
  • 方法3：单调递减队列，维护可能成为最大值的元素（时间O(n)，空间O(k)）- 最优解

代码实现：

java
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> deque = new LinkedList<>(); // 存下标，保证对应值递减
    for (int i = 0; i < n; i++) {
        // 移除队列中比当前元素小的，因为它们不可能成为最大值
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        // 移除超出窗口范围的队首
        if (deque.peekFirst() <= i - k) {
            deque.pollFirst();
        }
        // 窗口形成时记录最大值
        if (i >= k - 1) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

复杂度分析：时间复杂度 O(n)，每个元素最多入队出队各一次；空间复杂度 O(k)，队列最多存k个元素。

变体扩展：

  • 变体1：滑动窗口中位数
  • 变体2：最小栈
  • 变体3：每日温度（单调栈）
  • 变体4：柱状图中最大的矩形

Q6: 字符串的排列 「🟡 中级」 ​

题目描述：给你两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，s1 的排列之一是 s2 的子串。

考察点：滑动窗口、固定窗口、排列判断。

解题思路：

  • 方法：滑动窗口 + 数组计数，窗口大小固定为s1长度（时间O(m+n)，空间O(1)）- 最优解

代码实现：

java
public boolean checkInclusion(String s1, String s2) {
    if (s1.length() > s2.length()) return false;
    int[] need = new int[26];
    int[] window = new int[26];
    for (char c : s1.toCharArray()) {
        need[c - 'a']++;
    }
    int left = 0, valid = 0;
    int diffCount = 0;
    for (int n : need) if (n > 0) diffCount++;
    
    for (int right = 0; right < s2.length(); right++) {
        char c = s2.charAt(right);
        window[c - 'a']++;
        if (window[c - 'a'] == need[c - 'a']) {
            valid++;
        }
        while (right - left + 1 >= s1.length()) {
            if (valid == diffCount) {
                return true;
            }
            char d = s2.charAt(left);
            if (window[d - 'a'] == need[d - 'a']) {
                valid--;
            }
            window[d - 'a']--;
            left++;
        }
    }
    return false;
}

复杂度分析：时间复杂度 O(m+n)；空间复杂度 O(1)，字符集固定大小。

变体扩展：

  • 变体1：找到字符串中所有字母异位词
  • 变体2：最小覆盖子串
  • 变体3：无重复字符的最长子串
  • 变体4：字符串的排列（全排列回溯题）

Copyright © 2025-2026 京公网安备 11010102000001号 京ICP备2024078125号-1