stellogic的个人空间
子串
stellogic Two
  2025-09-23 01:41:36   2025-09-23 01:41:36    

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

简单的想法是，使用两层循环，外层循环确定子数组的起点，内层循环确定子数组的终点，并计算子数组的和。如果子数组的和等于 k，则计数器加一。这个时间复杂度应该是O(n^2)。

因为有很多重复计算，感觉可以动态规划。定义状态[i,j],表示从i到j的子数组的和，显然满足无后效性和最优子结构。状态转移方程是dp[i][j] = dp[i][j-1] + nums[j]。但是这样的话，时间复杂度还是O(n^2)。

正确的方法应该是前缀和。

利用前缀和。pre[i]表示从0到，i的和。那么如果[i,j]的和是k，那么pre[j] - pre[i-1] = k,即pre[i-1] = pre[j] - k。也就是说，对于我们遍历到的每个j，我们只要知道有多少个pre[i-1]等于pre[j]-k就行了。

可以用哈希表储存前缀和出现的次数。

步骤：

  1. 初始化map来存放前缀和，{前缀和：出现次数}
  2. 注意特殊边界，如果[0,0]子串时出现了pre[0] - pre[-1],pre[-1]没有定义，但实际上可以认为是所有元素出现之前，是0，因此可以先把{0}次数初始化为0
  3. 遍历数字，依次计算当前前缀和pre[j],查看哈希表是否存在pre[j] - k，添加结果;更新或者添加pre[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        int preSum = 0;
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            if (map.containsKey(preSum - k)){
                result += map.get(preSum - k);
            }
            map.put(preSum,map.getOrDefault(preSum,0) + 1);//map.get(preSum)++无意义
        }
        return result;
    }
}

注意：

  1. map.get()返回的是一个Integer对象，执行map.get()++执行了自动拆箱，相当于类似于3++，没有意义
  2. 可以使用getOrDefault(key,defaultValue)方法，如果key不在就默认成defaultValue。
  3. 时间复杂度O(n),空间复杂度O(n)

滑动窗口的最大值

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

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

每次只需要比较新进来的right指向的数和当前的最大值即可。时间复杂度O(n+k),空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int left = 0;
        int right = left + k - 1;
        int maxInt = Integer.MIN_VALUE;
        List<Integer> result = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            maxInt = Math.max(maxInt, nums[i]);
        }
        while (right < nums.length) {
            maxInt = Math.max(maxInt,nums[right]);
            result.add(maxInt);
            left++;
            right++;
        }
        return result.toArray(new Integer[0]);
    }
}

这个解法错误。没考虑如果左侧的出去的元素恰好是最大的元素
同时List的列表的转换为int[],要么遍历要么使用stream

必须每个窗口都同时遍历进行求最大值，时间复杂度只能说O(nk)

下面是正确解法

优先队列

使用一种能O(1)查找最大值的数据结构–优先队列（通常用 堆实现）

  1. 维护一个大顶堆，储存当前窗口的元素。堆顶始终是最大值
  2. 窗口向右移动时，新进入的元素入堆，同时要离开的元素移除
  3. 但是大顶堆只支持高效访问最大值，无法删除任意指定元素。可以储存而元素(数组，下标)。窗口移动时，查看堆顶。如果下标不在当前窗口，就弹出，继续查看新的堆顶，直到堆顶元素在窗口内
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
import java.util.PriorityQueue;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> b[0] - a[0]);
        int[] result = new int[nums.length - k +1];
        int left = 0;
        int right = left + k - 1;
        for (int i = left;i <= right;i++){
            pq.add(new int[]{nums[i],i});
        }
        result[left] = pq.peek()[0];
        left++;
        right++;
        while (right < nums.length){
            pq.add(new int[]{nums[right],right});
            while (!(pq.peek()[1] >= left && pq.peek()[1] <= right) ){
                pq.poll();
            }
            result[left] = pq.peek()[0];
            left++;
            right++;
        }
        return result;
    }
}

注意：

  1. 优先队列的初始化，参数应当是一个比较器。(a,b) -> returnValue 这个返回值如果为正，a在后b在前；如果为负，a在前b在后。可以这样记忆：假设a小，如果返回值是a-b,则为负，a在前，是升序（正好是默认的顺序，正好返回值a-b也是默认的顺序）；如果返回值是b-a,则为正，a在后，是降序（正好是不默认的顺序，正好b-a也不是和(a,b)相同的顺序)。

单调队列

使用一个双端队列。

在每次遍历时，把队列中相比于当前元素更早出现的、更小元素直接出列（因为当前元素必定比这个元素存在的时间长，并且值大，故这个元素不可能有机会成为最大值）

因此

  1. 队列存的是下标，不是值：我们不仅要直到值，也要直到索引，方便判断是否滑出了窗口
  2. 从队头到队尾，对应的值是单调递减的
  3. 为了保证上面的性质，每个新元素准备入队时 ，从队尾开始向前挑战，如果队尾的元素小于等于当前元素，说明队尾元素“又小又老”，直接出队。循环这个过程，直到队尾元素比当前元素大，或者队列为空。之后当前元素入队。
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
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        //处理首个窗口
        int left = 0;
        int right  = left + k - 1 ;
        for (int i = left; i <= right; i++) {
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[i]){
                deque.pollLast();
            }
            deque.addLast(i);
        }
        result[0] = nums[deque.peekFirst()];
        
        right++;
        left++;
        
        
        while (right < nums.length){
            // 移除队头如果队头索引滑出
            while (deque.getFirst() < left){//用if也行，但while更好理解
                deque.pollFirst();
            }
            //维护单调递减
            while (!deque.isEmpty() && nums[deque.getLast()] <= nums[right]){
                deque.pollLast();
            }
            deque.add(right);
            result[left] = nums[deque.getFirst()];
            left++;
            right++;
        }
        
        return result;
    }
}

时间复杂度O(n),虽然每个窗口的里面还有一次while循环，但每个窗口的循环次数不一定，总的来看每个元素最多入队依次和出队一次
空间复杂度O(k)，因为队头索引必然时最小的。所以他必然是第一个滑出的
一个元素的下标要想留在队列里，它必须满足一个苛刻的条件：它必须比所有在它之后入队的、且仍留在队列里的元素的值都大。
队头元素：它之所以能待在队头，是因为它从入队那一刻起，直到现在，所有后来者中没有一个比它更强（或者说，比它强的后来者把它前面的所有人都清除了，但没能清除它）。它是在这场“幸存者游戏”中活得最久（索引最小）的那个强者（值最大）。
队列中的其他元素：它们都是队头的“晚辈”（索引更大）。它们之所以能留在队列里，是因为它们比自己更晚的“晚辈”要强。

分块+预处理

后续补上

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”
解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。
示例 2：

输入：s = “a”, t = “a”
输出：”a”
解释：整个字符串 s 是最小覆盖子串。
示例 3:

输入: s = “a”, t = “aa”
输出: “”
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

思考：我的一个简单想法是先对t中每个字母计数，写入count_t，之后遍历s寻找字串。但这样 似乎时间复杂度要是O(n^2+m).还想能不能用滑动窗口，但似乎也无法降低复杂度。

但实际上滑动窗口是可以的。

使用[left,right]的窗口

  1. 使用哈希表needs储存t每个字符出现次数

    • window记录当前窗口每个字符出现次数
    • left right初始化为0
    • valid记录窗口中满足needs的种类数
    • start和len记录最小覆盖子串的起始位置和长度。len初始为max

  2. 扩展

    • 持续右移动right，把s[right] 移入窗口
    • 更新Windows中对应字符计数
    • 如果s[right]是t需要的字符，并且window中该字符的计数等于needs中该字符的计数，valid+1，表示又一个字符满足了要求

  3. 收缩

    • （每次right移动后，我们都进行一次判断））当valid的值等于needs中不同字符种类数，说明当前窗口已经满足要求，可以收缩窗口寻找更小的子串
    • 收缩前先更新最小子串记录：如果长度小于len，更新start和len（每个循环都会记录这个）
    • 向左移动left，s[left]出窗口
    • 更新window
    • 如果s[left]是t中需要的字符，并且移除前window中该字符的计数等于needs中计数，那么valid减一，表示有一个字符种类不再满足要求
    • 持续收缩直到不再满足要求。
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
42
43
44
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

class Solution {
    public String minWindow(String s, String t) {
        int left = 0;
        int right = 0;
        int valid = 0;
        int len = Integer.MAX_VALUE;
        int start = 0;
        Map<Character, Integer> window = new HashMap<>();
        Map<Character,Integer>  needs = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            needs.put(t.charAt(i),needs.getOrDefault(t.charAt(i),0) + 1);
        }
        
        for (; right < s.length(); right++) {
            window.put(s.charAt(right),window.getOrDefault(s.charAt(right),0) + 1);
            if (window.get(s.charAt(right)).equals(needs.getOrDefault(s.charAt(right), -1))){
                valid++;
            }
            while (valid == needs.size() && left <= right){
                if (len > right - left + 1){
                    len = right - left + 1;
                    start = left;
                }
                char l = s.charAt(left);
                if (needs.containsKey(l)){
                    if (window.get(l).equals(needs.get(l))){
                        valid--;
                    }
                }
                window.put(s.charAt(left),window.get(s.charAt(left)) - 1);
                left++;
            }
        }
        if (len == Integer.MAX_VALUE)
        {
            return "";
        }
        return s.substring(start,start + len);
    }
}
  1. 复杂度:时间O(m + n),首先needs的构建需要O(n),之后对于s，每个字符进出各一次，每个进出时其他操作均为O(1).空间复杂度O(k),k是t中不同字符的数量
  2. 注意哈希表的get()返回的是一个Integer对象，不能直接用==。使用Integer1.equals(Integer2)。==是在比较地址，如果Integer1和Integer2都是-128到127之间的数值，Java会把它们缓存起来，地址相同，所以==也会返回true。但是Integer和int可以用==，相当于自动拆箱了
子串
2025/09/23/子串/
作者
stellogic
发布于
2025-09-23 01:41
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 560. 和为 K 的子数组
  2. 2. 滑动窗口的最大值
    1. 2.1. 优先队列
    2. 2.2. 单调队列
    3. 2.3. 分块+预处理
  3. 3. 76. 最小覆盖子串
  1. 1. 560. 和为 K 的子数组
  2. 2. 滑动窗口的最大值
    1. 2.1. 优先队列
    2. 2.2. 单调队列
    3. 2.3. 分块+预处理
  3. 3. 76. 最小覆盖子串