【算法刷题系列】第2天 209. 长度最小的子数组, 59. 螺旋矩阵 II
Overview
学习内容
学习文档：
收获总结
- 滑动窗口：
在某些情况下，滑动窗口可以看作是一种特殊的双指针技术，其中两个指针 i 和 j（即左指针和右指针）从同一端开始，但移动的条件有所不同。滑动窗口的核心思想是通过右指针 j 不断向右扩展窗口，同时左指针 i 尽量向右收缩窗口，以找到满足特定条件的最小或最大窗口。
举例来说，假设你想找到数组 arr 中两个元素之间的差值等于 diff 的一对元素索引，这可以视为滑动窗口问题，右指针 j 用来扩展窗口，左指针 i 用来收缩窗口，直到找到满足条件的子数组。初始化时可以根据具体问题选择 i, j 都从 0, 0 开始，也可以 0, 1 这种情况。
题目解析
题目1：209. 长度最小的子数组
-
题目描述: 给定一个含有
n个正整数的数组nums和一个正整数target，找出该数组中满足其和≥ target的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回0。 -
示例:
1输入: target = 7, nums = [2,3,1,2,4,3] 2输出: 2 3解释: 子数组 [4,3] 是该条件下的长度最小的子数组。 -
解法总结: 该题可以通过滑动窗口技术来解决。我们使用两个指针
i和j，分别代表窗口的左右边界。首先，右指针j向右移动，扩展窗口，累加窗口内的元素和sum。当sum大于或等于target时，开始收缩窗口（移动左指针i），同时记录当前窗口的最小长度。通过这种方式，可以高效地找到满足条件的最短子数组长度。 这里需要注意的是，因为有可能第一个数就等于target，所以j也要从0开始，同时内侧判断条件也是for! -
代码实现:
1func minSubArrayLen(target int, nums []int) int { 2 i, j := 0, 0 3 sum := 0 4 min := len(nums) + 1 5 6 for j < len(nums) { 7 sum += nums[j] 8 9 for sum >= target { 10 // 只在 sum 等于 target 时更新 min 11 min = minValue(j-i+1, min) 12 sum -= nums[i] 13 i++ 14 } 15 16 j++ 17 } 18 19 // 最后检查是否找到了符合条件的子数组 20 if min == len(nums)+1 { 21 return 0 22 } else { 23 return min 24 } 25} 26 27func minValue(x, y int) int { 28 if x < y { 29 return x 30 } 31 return y 32} -
时间复杂度:
O(n)，因为每个元素在最坏情况下只会被访问两次，分别是被加入到窗口和从窗口中移除。 -
空间复杂度:
O(1)，仅使用了常数空间来存储索引、和以及最小长度。
题目2：59. 螺旋矩阵 II
-
题目描述: 给定一个正整数
n，生成一个包含1到n^2所有元素，且元素按顺时针顺序螺旋排列的n x n正方形矩阵。 -
示例:
1输入: n = 3 2输出: 3[ 4 [1, 2, 3], 5 [8, 9, 4], 6 [7, 6, 5] 7] -
解法总结: 这段代码的目的是生成一个
n x n的螺旋矩阵，矩阵中的元素从 1 开始，按顺时针方向从外向内依次填充。具体来说，代码通过控制矩阵的四个边界（上、下、左、右）来逐步缩小范围。每次循环依次填充当前边界，从左到右、从上到下、从右到左、从下到上，直到所有元素填满为止。在填充过程中，每个方向的边界都会向内收缩一行或一列，确保后续填充在正确的范围内进行。最终，当num超过目标值（n * n）时，填充过程结束，返回生成的螺旋矩阵。 在实现过程中，有几个关键要点和注意事项。首先是边界的初始化和更新，确保在每次填充完一个方向后正确地调整top、bottom、left和right的值，以防止重复填充或越界。其次，在循环过程中需要时刻检查num的值，以确保填充过程不会超出范围。此外，需要特别处理小矩阵的特殊情况，如n = 1或n = 0，以保证代码的通用性和正确性。最后，由于算法的时间和空间复杂度均为O(n^2)，这意味着该算法可以有效地处理中小规模的矩阵生成任务，但在非常大的n时需要考虑性能问题。 -
代码实现:
1func generateMatrix(n int) [][]int { 2 // Init 3 top, bottom, left, right := 0, n-1, 0, n-1 4 num := 1 5 target := n * n 6 7 matrix := make([][]int, n) 8 9 for i := 0; i <= n-1; i++ { 10 matrix[i] = make([]int, n) 11 } 12 13 for num <= target { 14 for i := left; i <= right; i++ { 15 matrix[top][i] = num 16 num++ 17 } 18 top++ 19 20 for i := top; i <= bottom; i++ { 21 matrix[i][right] = num 22 num++ 23 } 24 right-- 25 26 for i := right; i >= left; i-- { 27 matrix[bottom][i] = num 28 num++ 29 } 30 bottom-- 31 32 for i := bottom; i >= top; i-- { 33 matrix[i][left] = num 34 num++ 35 } 36 left++ 37 } 38 39 return matrix 40} -
时间复杂度:
O(n^2)，因为需要填充整个n x n的矩阵。 -
空间复杂度:
O(n^2)，用于存储生成的螺旋矩阵。