代码随想录算法训练营第二天 | 209. 长度最小的子数组、59. 螺旋矩阵 II

209. 长度最小的子数组

题目链接：209

1、题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

2、思路

1️⃣ 暴力法，两个for循环嵌套，时间复杂度$O(n^2)$
2️⃣ 题目基本是根据连续子序列的情况，不断调节子序列的起始和终止位置：滑动窗口
模板：

3、code

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:# 找一个数组的满足条件的最短或者最长连续子数组：滑动窗口minlen = float('inf')start = 0sum_sub = 0for end in range(0,len(nums)):sum_sub += nums[end]while sum_sub >= target:minlen = min(minlen, end-start+1)sum_sub -= nums[start]start += 1if minlen <= len(nums):return minlenelse:return 0

4、复杂度分析

• 时间复杂度：
  每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)
• 空间复杂度：没有创建数组$O(1)$

LC59 螺旋矩阵 II

题目链接：59

1、题目描述

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix
示例 1：

2、思路

要控制每次循环的区间范围（循环不变量）
按照左闭右开的原则，来画一圈，大家看一下：

3、code

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:# 首先先初始化一个全是0的nxn二维矩阵mat = [[0 for _ in range(n)] for _ in range(n)]# 定义每一圈的起始点坐标start_x = 0start_y = 0# 定义表示不同圈的每一条边的倒数第二个节点的偏移量# 比如第1圈是j = (n-1) - 1# 第2圈就是j = (n-1) - 2offset = 1# 定义要往矩阵中填入的数count = 1loop = n //2# 循环开始for time in range(0,loop):# 填充上行从左到右:横坐标不变且是start_x，纵坐标从start_y到(n - 1) - 1for j in range(start_y, n - offset):# 因为range“顾头不顾腚”所以可以少写一个-1mat[start_x][j] = countcount += 1# 填充右列从上到下：横坐标从start_x到(n-1)-offset，纵坐标不变且是上行最后一个元素的坐标加一(j = n - offset)                # 此时到达了上行的倒数第二个元素(start_x,j = (n-1)-offset)# 那么右列的第一个元素就是(start_x,n - offset)for i in range(start_x, n - offset):mat[i][n - offset] = countcount += 1# 填充下行从右到左：横坐标不变是上列最后一个元素的横坐标加一(i = n - offset)，纵坐标从上一次的j = n - offset 一直减到start_y + 1for j in range(n - offset, start_y, -1):mat[n - offset][j] = countcount += 1# 填充左列从下到上：横坐标从上一次的i = n - offset一只减到start_x + 1，纵坐标不变就是上一行最后一个元素的纵坐标减一（start_y）for i in range(n - offset, start_x, -1):mat[i][start_y] = countcount += 1# 更新起始点坐标start_x += 1start_y += 1offset += 1mid = n // 2if n%2 != 0:mat[mid][mid] = count   return mat    

4、复杂度分析

1️⃣ 时间复杂度：$n/2\ast 4\ast (n-k)=n^2$
2️⃣ 空间复杂度：1