题目977.有序数组的平方

1. 最直白的想法：所有元素平方之后用快排排个序，时间复杂度是O(n+nlogn)，快排的时间复杂度后面要复习！
2. 双指针解法（时间复杂度为O(n)）
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        k = len(nums) - 1
        i, j = 0, len(nums) - 1
        res = [0] * len(nums) #这里为什么要提前初始化一个数组，是因为在原数组上进行元素的平方会改变进入计算的元素，也就是说，有可能这个元素是已经被平方之后才拿来进行比较大小。题外话，也可使用float('inf') 来定义一个无穷大的浮点数作为安全的初试阈值或比较值
        while (i <= j):
            if nums[i]**2 > nums[j]**2:
                res[k] = nums[i]**2
                i = i + 1
            else:
                res[k] = nums[j]**2
                j = j - 1
            k -= 1
        return res

题目209.长度最小的子数组

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        right = 0
        l = len(nums)
        cur_sum = 0
        min_len=float('inf')
        while right < l:
            cur_sum += nums[right]
            while cur_sum >= target: #如果当前窗口的值大于target了，窗口就要缩小
                min_len=min(min_len, right-left+1)
                cur_sum -= nums[left]
                left += 1 
            right += 1
        return min_len if min_len != float('inf') else 0
        
时间复杂度：不是O(n^2),不要以为for里放一个while就以为是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

59.螺旋矩阵II

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums = [[0] * n for i in range(n)]
        loop = n //2
        mid = n // 2
        startx = 0
        starty = 0
        offset = 1
        count = 1
        while offset <= loop:
            for i in range(starty, n-offset):
                nums[startx][i] = count
                count += 1
            for i in range(startx, n-offset):
                nums[i][n-offset] = count
                count += 1
            for i in range(n-offset, starty,-1):
                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
            offset+=1
        if n % 2 != 0 :         # n为奇数时，填充中心点
            nums[mid][mid] = count 
        return nums
        
# 本题重点：startx、starty、offset三个变量同时更新，可以实现循环不变量（即每一条边的处理规则或者说边界一致）

明天补上数组专题的总结！！！