代码随想录算法训练营day2（数组）

长度最小的子数组

• https://leetcode.cn/problems/minimum-size-subarray-sum/

思路

• 使用滑动窗口，left表示滑动窗口的起始点，right表示滑动窗口的终点

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0     # left表示滑动窗口的起始点
        res = float('inf')   # float('inf')表示无穷大
        total = 0    # 记录滑动窗口中的和
        length = len(nums)
        for right in range(length):   # right表示滑动窗口的终点
            total += nums[right]
            while total >= target:
                l = right - left + 1
                res = min(l, res)
                total -= nums[left]
                left += 1
        if res == float('inf'):   # 说明在遍历过程中，初始的res始终没有被替换，即nums的总和小于target
            return 0
        else:                # res被替换了，说明有满足条件的
            return res

螺旋矩阵

• https://leetcode.cn/problems/spiral-matrix-ii/

思路

• 每遍历一条边时，保持循环不变量原则，即每一条边都遵循左闭右开[)的原则

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        arr = [ [None]*n for _ in range(n)]   # 先申请好一段二维数组
        startx, starty = 0, 0   # 每遍历一圈的起始位置
        offset = 1               # 右开
        count = 1               # 技术器
        loop = n // 2           # 总共螺旋的圈数
        mid = n // 2             # 若n为奇数，则最中间元素的坐标
        while loop > 0:
            for y in range(starty, n - offset):    # 上边
                arr[startx][y] = count
                count+=1
            for x in range(startx, n - offset):   # 右边
                arr[x][n - offset] = count
                count+=1
            for y in range(n - offset, starty, -1):   # 下边
                arr[n - offset][y] = count
                count+=1
            for x in range(n - offset, startx, -1):   # 左边
                arr[x][starty] = count
                count+=1
            startx += 1
            starty += 1
            offset += 1
            loop -= 1
        if n%2 == 1:   # 若n为奇数
            arr[mid][mid] = n*n
        return arr

总结