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

題目鏈接：209

1、題目描述

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

2、思路

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

3、code

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

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

LC59 螺旋矩陣 II

題目鏈接：59

1、題目描述

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

2、思路

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

3、code

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

4、復(fù)雜度分析

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