还是用双指针解决问题，不过这次用双指针形成个滑动窗口

看来数组问题用双指针解决还挺常见

209. 长度最小的子数组

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

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 子数组需要连续
        # 使用双指针，slow指针用于删除元素，fast指针用来添加元素；若添加后的元素让总sumOfnums大于等于target，则可以进行pop（删除），并保持删除后的sum仍大于等于target

        # sumOfnums = sum(nums)
        slow = 0
        L = len(nums)
        res = float('inf')

        # if sumOfnums < target:
        #     return 0

        newSum = 0

        # 循环pop
        for fast in range(L):
            newSum += nums[fast]

            while newSum >= target:
                res = min(res, fast - slow + 1) 
                newSum -= nums[slow]
                slow += 1
                # newSum在减掉nums[slow]后，不一定会再大于target，不需要再将res-1
                # res -= 1
        
        # 通过让res与inf比较，从而得知是否存在长度最小的子数组满足条件，否则就返回0；
        # 这样的好处是不需要对整个数组求和
        if res != float('inf'):
            return res
        return 0

59. 螺旋矩阵 II

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

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

示例 1：

img

1
2
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1
2
输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 一个大循环
        # 包含四个for循环

        loop, mid = n//2, n//2   #迭代次数，n为奇数时，矩阵的中心点
        index = 1
        startx, starty = 0, 0
        nums = [[0] * n for _ in range(n)]
        for offset in range(1, loop + 1):
            # 第一行
            for i in range(starty, n - offset):
                nums[startx][i] = index
                index += 1
            # 最后一列
            for j in range(startx, n - offset):
                nums[j][n - offset] = index
                index += 1
            # 最后一行
            for i in range(n - offset, starty, -1):
                nums[n - offset][i] = index 
                index += 1
            # 第一列
            for j in range(n - offset, startx, -1):
                nums[j][starty] = index
                index += 1
            startx += 1
            starty += 1
        
        if n % 2 != 0:
            nums[mid][mid] = index
        return nums