LeetCode 热题 HOT100（三）：子串进阶与普通数组（Go 实现）

🥰个人主页：会编程的土豆（欢迎来访）
💎作者简介：后端学习者
❄️个人专栏：数据结构与算法，数据库，leetcode
✨那些你一个人走过的夜路，终将化作照亮未来的光

本文覆盖力扣「热题 100」学习计划第11～15题，全部使用Go实现。

第 10 题「和为 K 的子数组」见上一篇；本篇从滑动窗口最大值开始。

题单入口：LeetCode 热题 100

239. 滑动窗口最大值

难度：困难
标签：队列、数组、滑动窗口、单调队列、堆（优先队列）
题目链接：239. 滑动窗口最大值

题目描述

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

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

示例：

输入：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

思路分析

暴力每个窗口扫一遍是 O(nk)。最优解用单调队列（存下标）：

1. 队列内下标对应的值从大到小
2. 新元素入队前，从队尾弹出所有「值 ≤ 当前值」的下标（它们不可能再成为最大值）
3. 队头若滑出窗口（下标 ≤ i-k），弹出
4. 窗口形成后，队头就是当前最大值下标

Go 代码

func maxSlidingWindow(nums []int, k int) []int { n := len(nums) res := make([]int, 0, n-k+1) deque := make([]int, 0) // 存下标，对应值单调递减 for i, num := range nums { // 弹出队尾较小元素 for len(deque) > 0 && nums[deque[len(deque)-1]] <= num { deque = deque[:len(deque)-1] } deque = append(deque, i) // 弹出滑出窗口的队头 if deque[0] <= i-k { deque = deque[1:] } // 窗口已形成 if i >= k-1 { res = append(res, nums[deque[0]]) } } return res }

复杂度

• 时间复杂度：O(n)，每个下标最多入队、出队一次
• 空间复杂度：O(k)

76. 最小覆盖子串

难度：困难
标签：哈希表、字符串、滑动窗口
题目链接：76. 最小覆盖子串

题目描述

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

注意：对于t中重复字符，子串中该字符数量必须不少于t中该字符数量。

示例：

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

思路分析

变长滑动窗口经典题：

1. 统计t的字符需求need，以及还需满足的「有效字符种类数」needKinds
2. 右指针扩张，更新窗口计数；某字符刚好凑齐时valid++
3. 当valid == needKinds，说明窗口已覆盖，尝试收缩左指针，并记录最短子串
4. 左端字符不够时valid--，继续扩张

Go 代码

func minWindow(s string, t string) string { if len(s) < len(t) || len(t) == 0 { return "" } need := make(map[byte]int) for i := 0; i < len(t); i++ { need[t[i]]++ } needKinds := len(need) window := make(map[byte]int) valid := 0 left := 0 start, minLen := 0, len(s)+1 for right := 0; right < len(s); right++ { c := s[right] if _, ok := need[c]; ok { window[c]++ if window[c] == need[c] { valid++ } } for valid == needKinds && left <= right { if right-left+1 < minLen { minLen = right - left + 1 start = left } d := s[left] left++ if _, ok := need[d]; ok { if window[d] == need[d] { valid-- } window[d]-- } } } if minLen == len(s)+1 { return "" } return s[start : start+minLen] }

复杂度

• 时间复杂度：O(|s| + |t|)
• 空间复杂度：O(|Σ|)

53. 最大子数组和

难度：中等
标签：数组、分治、动态规划
题目链接：53. 最大子数组和

题目描述

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

思路分析

Kadane 算法（可看作一维 DP）：

• cur：以当前元素结尾的最大子段和
• 转移：cur = max(nums[i], cur + nums[i])
• 含义：前面累加和若为负，不如从当前重新开始

同时用ans维护全局最大值。

Go 代码

func maxSubArray(nums []int) int { cur, ans := nums[0], nums[0] for i := 1; i < len(nums); i++ { if cur > 0 { cur += nums[i] } else { cur = nums[i] } if cur > ans { ans = cur } } return ans }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

56. 合并区间

难度：中等
标签：数组、排序
题目链接：56. 合并区间

题目描述

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

思路分析

1. 按区间左端点排序
2. 遍历：若当前区间与结果中最后一个区间重叠（start <= lastEnd），则合并，更新右端点为两者较大值
3. 否则直接追加新区间

Go 代码

func merge(intervals [][]int) [][]int { if len(intervals) == 0 { return nil } sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) res := [][]int{intervals[0]} for i := 1; i < len(intervals); i++ { last := res[len(res)-1] cur := intervals[i] if cur[0] <= last[1] { if cur[1] > last[1] { last[1] = cur[1] } } else { res = append(res, cur) } } return res }

记得导入：import "sort"

复杂度

• 时间复杂度：O(n log n)，主要在排序
• 空间复杂度：O(log n)（排序栈空间，不计返回数组）

189. 轮转数组

难度：中等
标签：数组、数学、双指针
题目链接：189. 轮转数组

题目描述

给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

示例：

输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]

思路分析

经典「三次反转」，空间 O(1)：

1. 整体反转：[1,2,3,4,5,6,7]→[7,6,5,4,3,2,1]
2. 反转前k个：[5,6,7,4,3,2,1]
3. 反转后n-k个：[5,6,7,1,2,3,4]

注意先对k取模，避免k >= n。

Go 代码

func rotate(nums []int, k int) { n := len(nums) k %= n reverse(nums, 0, n-1) reverse(nums, 0, k-1) reverse(nums, k, n-1) } func reverse(nums []int, left, right int) { for left < right { nums[left], nums[right] = nums[right], nums[left] left++ right-- } }

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

小结

前 15 题进度

下一篇可继续写普通数组剩余题（除自身以外数组的乘积、缺失的第一个正数）以及矩阵、链表专题。

如果对你有帮助，欢迎点赞收藏，一起把 Hot100 刷完！