209. 長度最小的子數(shù)組

題目鏈接：209

1、題目描述

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。找出該數(shù)組中滿足其總和大于等于 target 的長度最小的 子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0。
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

2、思路

1?? 暴力法，兩個for循環(huán)嵌套，時間復(fù)雜度$O(n^2)$
2?? 題目基本是根據(jù)連續(xù)子序列的情況，不斷調(diào)節(jié)子序列的起始和終止位置：滑動窗口
模板：

3、code

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:# 找一個數(shù)組的滿足條件的最短或者最長連續(xù)子數(shù)組：滑動窗口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、復(fù)雜度分析

• 時間復(fù)雜度：
  每個元素在滑動窗后進(jìn)來操作一次，出去操作一次，每個元素都是被操作兩次，所以時間復(fù)雜度是 2 × n 也就是O(n)
• 空間復(fù)雜度：沒有創(chuàng)建數(shù)組$O(1)$

LC59 螺旋矩陣 II

題目鏈接：59

1、題目描述

給你一個正整數(shù) n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix
示例 1：

2、思路

要控制每次循環(huán)的區(qū)間范圍（循環(huán)不變量）
按照左閉右開的原則，來畫一圈，大家看一下：

3、code

class Solution:def generateMatrix(self, n: int) -> List[List[int]]:# 首先先初始化一個全是0的nxn二維矩陣mat = [[0 for _ in range(n)] for _ in range(n)]# 定義每一圈的起始點坐標(biāo)start_x = 0start_y = 0# 定義表示不同圈的每一條邊的倒數(shù)第二個節(jié)點的偏移量# 比如第1圈是j = (n-1) - 1# 第2圈就是j = (n-1) - 2offset = 1# 定義要往矩陣中填入的數(shù)count = 1loop = n //2# 循環(huán)開始for time in range(0,loop):# 填充上行從左到右:橫坐標(biāo)不變且是start_x，縱坐標(biāo)從start_y到(n - 1) - 1for j in range(start_y, n - offset):# 因為range“顧頭不顧腚”所以可以少寫一個-1mat[start_x][j] = countcount += 1# 填充右列從上到下：橫坐標(biāo)從start_x到(n-1)-offset，縱坐標(biāo)不變且是上行最后一個元素的坐標(biāo)加一(j = n - offset)                # 此時到達(dá)了上行的倒數(shù)第二個元素(start_x,j = (n-1)-offset)# 那么右列的第一個元素就是(start_x,n - offset)for i in range(start_x, n - offset):mat[i][n - offset] = countcount += 1# 填充下行從右到左：橫坐標(biāo)不變是上列最后一個元素的橫坐標(biāo)加一(i = n - offset)，縱坐標(biāo)從上一次的j = n - offset 一直減到start_y + 1for j in range(n - offset, start_y, -1):mat[n - offset][j] = countcount += 1# 填充左列從下到上：橫坐標(biāo)從上一次的i = n - offset一只減到start_x + 1，縱坐標(biāo)不變就是上一行最后一個元素的縱坐標(biāo)減一（start_y）for i in range(n - offset, start_x, -1):mat[i][start_y] = countcount += 1# 更新起始點坐標(biāo)start_x += 1start_y += 1offset += 1mid = n // 2if n%2 != 0:mat[mid][mid] = count   return mat    

4、復(fù)雜度分析

1?? 時間復(fù)雜度：$n/2?4?(n?k)=n^2$
2?? 空間復(fù)雜度：1