跳到主要内容

子串问题

子串类题目通常涉及对连续片段的处理，可能结合前缀和、滑动窗口、或单调队列等技巧。

560. 和为 K 的子数组 (Subarray Sum Equals K)​

题目描述​

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中连续的非空序列。

解题思路​

使用前缀和加哈希表优化的方法。记录前缀和出现的次数。当遍历到某一位时，若 sum - k 存在于哈希表中，则说明存在子数组和为 k。

Java 代码实现​

class Solution {
    public int subarraySum(int[] nums, int k) {
        int res = 0, pre = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int num : nums) {
            pre += num;
            if (map.containsKey(pre - k)) res += map.get(pre - k);
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return res;
    }
}

239. 滑动窗口最大值 (Sliding Window Maximum)​

题目描述​

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。返回滑动窗口中的最大值。

解题思路​

使用单调双端队列（Deque）。队列中存放数组下标，保证下标对应的元素是递减的。窗口滑动时，从右侧移除所有比当前元素小的元素，从左侧移除刚好滑出窗口的元素。

Java 代码实现​

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for (int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            if (i > 0 && deque.peekFirst() == i - 1) deque.removeFirst();
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[j]) deque.removeLast();
            deque.addLast(j);
            if (i >= 0) res[i] = nums[deque.peekFirst()];
        }
        return res;
    }
}

76. 最小覆盖子串 (Minimum Window Substring)​

题目描述​

给你一个字符串 s 、一个字符串 t 。返回 s 中包含 t 所有字符的最小子串。如果 s 中不存在符合条件的子串，则返回空字符串 "" 。

解题思路​

典型的变长滑动窗口。使用哈希表（或数组）记录 t 中的字符频次需求。移动右边界直至窗口满足 t，然后尽量收缩左边界以获得最小长度。

Java 代码实现​

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) return "";
        int[] need = new int[128], have = new int[128];
        for (char c : t.toCharArray()) need[c]++;
        int count = 0, minLen = Integer.MAX_VALUE, start = 0, left = 0, right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            if (need[c] == 0) { right++; continue; }
            if (have[c] < need[c]) count++;
            have[c]++; right++;
            while (count == t.length()) {
                if (right - left < minLen) {
                    minLen = right - left; start = left;
                }
                char d = s.charAt(left);
                if (need[d] == 0) { left++; continue; }
                if (have[d] == need[d]) count--;
                have[d]--; left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}