977.有序数组的平方

方法1：暴力法

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:

        # 写法1
        for i in range(len(nums)):
            nums[i] = pow(nums[i], 2)
        nums.sort()
        return nums
        
        # 极简写法2
        return sorted([i**2 for i in nums])

方法2：双指针法

左右指针同时向中间移动

# while循环
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        
        left = 0
        right = len(nums) - 1
        result = [0] * len(nums)
        i = len(nums) - 1

        while left <= right: #left和right指向同一个元素时，元素也要被处理
            if pow(nums[left], 2) > pow(nums[right], 2):
                result[i] =  pow(nums[left], 2)
                left += 1
            else:
                result[i] = pow(nums[right], 2)
                right -= 1
            i -= 1
        return result

# for循环
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:

        left = 0
        right = len(nums) - 1
        result =[0] * len(nums) # 构造新数组存放结果

        for i in range(len(nums) - 1, -1, -1): # 步长为-1，i由大到小循环，eg 3 2 1 0
            if pow(nums[left], 2) > pow(nums[right], 2):
                result[i] =  pow(nums[left], 2)
                left += 1
            else: # 要考虑 小于 和 等于 两种情况，元素相等，要继续移动right
                result[i] = pow(nums[right], 2)
                right -= 1
        return result

时间复杂度为O(n)

209.长度最小的子数组

滑动窗口法，本质还是双指针法，和27不同的是，i，j两个指针都是满足条件才移动
先向后移动 j，sum_nums 满足条件后，开始移动 i，压缩窗口内的和
i：指针起始位置
j：指针结束位置

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        
        result = float('inf') # 赋值result极大值
        i, sum_nums = 0, 0

        for j in range(len(nums)):
            sum_nums += nums[j] # 前j个数值累加
            while sum_nums >= target: #while循环是在当前区间找到最小值
                result = min(result, j-i+1) 
                sum_nums -= nums[i] # sum在跳出while循环后，存放的是i到j区间的和
                i += 1
        return 0 if result == float('inf') else result

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

59.螺旋矩阵II

循环不变量原则
每条边按左闭右开的原则处理，不处理最后一个点

旋转的圈数为 n // 2
第一层循环：控制循环几圈
第二层循环：生成每条边

class Solution:
    def generateMatrix(self,  n: int) -> List[List[int]]:

        # arry[startx][starty]
        #       行      列
        loop, mid = n // 2, n // 2
        startx, starty = 0, 0
        count = 1
        nums = [[0] * n for _ in range(n)]

        for offset in range(1, loop +1):
            # 向右移动
            for i in range(starty, n - offset): # 列变化，用starty
                nums[starty][i] = count # 行不变（startx），列移动（i）
                count += 1
            # 向下移动
            for i in range(startx, n - offset): # 行变化，用startx
                nums[i][n - offset] = count # 行移动（i），列不变，列已经移动到n - offset的位置
                count += 1
            # 向左移动
            for i in range(n - offset, starty, -1): # 列变化，用starty
                nums[n - offset][i] = count
                count += 1
            # 向上移动
            for i in range(n - offset, startx, -1):
                nums[i][starty] = count
                count += 1
            startx += 1 # 要更新起始点
            starty += 1 
        if n % 2 == 1:
            nums[mid][mid] = count
        return nums