本系列是代码随想录算法训练营的学习笔记之day2，主要记录一下刷题的过程，以及核心知识点和一些值的记录的问题。

代码随想录的资源都是免费的，具体可以看参考链接【1】。

今日知识点

数组理论基础：

• 存放相同类型数据；
• 在内存上是连续的（二维数组视语言而定）；
• 数组元素不能删除，只能覆盖；

今日题目

1. 有序数组的平方（977）

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

解题思路

• 原题目说非递减顺序，所以排序后的数组最大值应该是从原数组的两端得到的（负值平方后也许是最大值）；
• 输出的结果要求是非递减顺序，所以可以用双指针法，一直比较原始数组两端的数据平方后的大小，把大的放在输出结果的最后（所以这里要预先构造好相应的数组用来存放数据）；

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l,r,k = 0, len(nums)-1,len(nums)-1
        re = [0]*(k+1)
        while l<=r:
            ls,rs = nums[l]**2,nums[r]**2
            if ls>rs:
                re[k]=ls
                k -= 1
                l += 1
            else:
                re[k]=rs
                k -= 1
                r -= 1
        return re 

2. 长度最小的子数组（209）

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

解题思路

• 注意题目说的，数组都是正整数，target也是正整数；
• 找出满足条件的连续子数组，因为是连续数组，所以用双指针法（头尾）；
• 返回的是新数组的长度，不是新数组！

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l,r = 0, len(nums)-1
        index = 0
        sum_ = 0
        res = float('inf')

        while l<=r:
            sum_ += nums[l]
            while sum_>= target:
                res = min(res,l-index+1)
                sum_ = sum_ - nums[index]
                index += 1
            l +=1

        return 0 if index==0 else res

• 这里的双指针指的是最小子数组的首尾两个指针；
• 满足条件的可能有很多个子串，我们要找到长度最小的那个，所以在内层的while循环中要记录下当前的子串长度（l-index+1），并且与上一个满足条件的长度进行（res）对比；
• 返回的时候要注意，需要考虑到没有满足条件的情况（返回0）；

3. 螺旋矩阵（59）

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

链接：https://leetcode.cn/problems/spiral-matrix-ii/

解题思路

• 正整数n，生成n**2个元素，注意预先构造矩阵；
• 元素是顺时针排序。

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        re = [[0]*n for _ in range(n)]
        stx,sty = 0,0
        loop = n//2
        count = 1

        for offset in range(1,loop+1):
            for i in range(sty,n-offset):
                re[stx][i] = count
                count += 1
            for i in range(stx,n-offset):
                re[i][n-offset] = count
                count +=1
            for i in range(n-offset,sty,-1):
                re[n-offset][i] = count
                count += 1
            for i in range(n-offset,stx, -1):
                re[i][sty] = count
                count += 1
            stx += 1
            sty += 1
        if n%2==1:
            re[n//2][n//2]=n**2
        return re

• 要理解螺旋是通过什么变量来控制的（stx，sty和offset）；
• offset要从1开始，且能取到n的一半（非常重要）！
• 如果n是奇数，要注意给最中间的元素进行赋值。

补充知识点

1. 下换线_的作用是什么？

占位。

今日思考

1. 对于区间的遍历时，用for还是while更好？

对于python，个人感觉用for更好，因为可以用range，如果用while，记得要在最后+1。

2. 二分查找的时候区间的划分其本质是什么？

遍历到所有元素，做到查无遗漏。（再次牢记！）

3. 螺旋矩阵为什么要设置offset？

这样子可以保存每次在遍历下标的时候四条边是一样的长度，且边界值更好确定。

参考

【1】代码随想录：https://programmercarl.com/