977有序数组的平方
题目链接：
https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解：
https://www.bilibili.com/video/BV1QB4y1D7ep
思路
- 虽然数组是非递减的，但是要考虑到数组的左半部分是负数的情况，比如数组是[-100，-50，0，10]，非递减，但是平方之后，为[10000，2500，0，100]，显然不是非递减的。因此我们不能从第一个数遍历到最后一个数，依次求平方，这种方法只适用于数组中的数字全部大于0的情况。
- 假设数组是从负数过渡到正数，那么求平方后，最大的数应该出现在最左边或最右边。对于全为正数或全为负数的情况，可以看作它的一种特殊形式。
- 因此我们选择用左右指针从两头向中间进行收缩，依次比对平方后的数值，满足要求就加入结果集。
- 注意这里while中为什么是<=号，而不是<号？考虑一种极端情况，即全为负数的情况，当处理完倒数第二个数，left向后移动，此时left和right都指向了最后一个数，即left=right。如果此时退出循环，那么就会漏掉最后一个数。所以while中的条件是left<=right。
class Solution(object):
def sortedSquares(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ans = []
n = len(nums)
if n == 0:
return nums
left = 0
right = n-1
while(left <= right):
left_num = nums[left] * nums[left]
right_num = nums[right] * nums[right]
if left_num >= right_num:
ans.append(left_num)
left += 1
else:
ans.append(right_num)
right -= 1
return ans[::-1]
209长度最小的子数组
题目链接：
https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：
https://www.bilibili.com/video/BV1tZ4y1q7XE
思路
- 因为题目说了是正整数的数组和正整数的target，那么当使用两个指针作为窗口的起始和结束时，右指针向前走，一定会使窗口中的元素和变大，左指针向前走，一定会使窗口中的元素和变小。
- 因此，我们从位置0开始，每次让右指针向前走一位，如果窗口中的元素和小于target，那么右指针继续向前走。
- 如果窗口中的元素和大于等于target，那么此时记录窗口的长度，然后左指针向前走，收缩窗口，记录窗口长度，收缩窗口......直到窗口中的元素和小于target。那么最终我们会得到一个全局最短的窗口长度。
- 题目要求，如果没有满足要求的窗口，那么返回0。所以这里我对最小长度的初始化就是0，因为我们遍历中计算出的窗口长度最小也是1，即窗口中只有一个数。所以，如果我们能找到符合要求的窗口，窗口长度一定是大于等于1的。所以这里初始化为0没有问题。
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
n = len(nums)
left = 0
ans = 0 # 用于记录滑动窗口中的和
minLen = 0 # 用于记录最小长度
for right in range(0, n):
ans += nums[right] # right向前走，更新窗口的和
if ans < target: # 如果窗口的和小于target，那么right继续向前走
continue
# 如果窗口和大于target，此时left持续向前走，收缩窗口，并更新窗口长度
while(ans >= target):
# right-left+1是窗口的长度
minLen = min(right-left+1, minLen) if minLen != 0 else right-left+1
# 窗口收缩
ans -= nums[left]
left += 1
return minLen
59螺旋矩阵II
题目链接：
https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：
https://www.bilibili.com/video/BV1SL4y1N7mV/
思路
- 这里用的是螺旋矩阵的通用写法，注意填充的时候要有原则，以最外面一圈为例，填充第一行时，不填充最后一列的元素；填充最右列的时候，不填充最后一行的元素。四个方向都按照这个原则，就不会写乱。
- while的条件为什么是top<bottom和left<right，而不是top<=bottom和left<=right？
- 若n为偶数，以2x2的矩阵为例，四个方向打印一圈后，top=1，right=0，bottom=0，left=1，所以不管使用<还是<=，都会退出循环，是没有影响的。
- 重点在于n为奇数的情况，以3x3的矩阵为例，四个方向打印一圈后，top=1，right=1，bottom=1，left=1，即，若n为奇数，剩中间一个空的时候，四个指针的数值一定是相同的，即在最中心的位置相遇。如果使用<号，此时不会继续循环，那么我们直接对最后一个空位置赋值即可；如果使用<=号，那么此时仍旧会进入循环，我们前面说过，比如填充第一行时，我们其实只对[left，right-1]的位置进行了填充，即[left，right)的左闭右开区间。那么当四个指针相遇时，左闭右开的区间其实已经没有意义了，就不需要再进入了。
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
if n == 0:
return []
maxtrix = [[0] * n for i in range(n)]
top = 0
right = n-1
bottom = n-1
left = 0
count = 1
while(top < bottom and left < right):
for i in range(left, right):
maxtrix[top][i] = count
count += 1
for j in range(top, bottom):
maxtrix[j][right] = count
count += 1
for p in range(right, left, -1):
maxtrix[bottom][p] = count
count += 1
for q in range(bottom, top, -1):
maxtrix[q][left] = count
count += 1
# 一圈转完之后，再更新指针
top += 1
right -= 1
bottom -= 1
left += 1
# 如果n为奇数，那么还剩中间一个位置需要填
if n % 2 == 1:
maxtrix[top][top] = count
return maxtrix
54螺旋矩阵
思路
- 这道题由于矩阵是mxn的，转圈时区间的定义稍有不同。目前也没有想到比较好的解释，后面再补充吧。
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return []
m = len(matrix)
n = len(matrix[0])
ans = []
top = 0
right = n-1
bottom = m-1
left = 0
while(top <= bottom and left <= right):
for i in range(left, right+1):
ans.append(matrix[top][i])
top += 1
for i in range(top, bottom+1):
ans.append(matrix[i][right])
right -= 1
if top <= bottom:
for i in range(right, left-1, -1):
ans.append(matrix[bottom][i])
bottom -= 1
if left <= right:
for i in range(bottom, top-1, -1):
ans.append(matrix[i][left])
left += 1
return ans
