27.移除元素
思路1：遇到数值符合的元素，两两交换从而后移一位
因为要原地操作，所以一开始的思路就是遍历数组，遇到数值符合的元素，将其和后面的元素两两交换从而实现后移一位。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
equal_nums = 0 # 数值等于val的元素个数
for i in range(len(nums)-1):
if nums[i] == val:
tmp = nums[i]
nums[i] = nums[i+1]
nums[i+1] = tmp
equal_nums += 1
if nums[len(nums)-1] == val:
equal_nums += 1
return len(nums)-equal_nums
这个代码的问题就是，如果在数组中遇到重复的数值等于val的元素，这个两两交换且后移一位就会失效。
思路2：双指针，快指针遍历数组，慢指针指向非val元素结束的位置
所以想到一个快指针和一个慢指针。快指针遍历数组元素，当遇到不等于val的元素时，就将该元素复制到慢指针的位置，然后慢指针前进一步。这样最后慢指针的位置就是所有非val元素的长度，同时数组的前k个都是非val的。
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
fast = slow = 0
# 快指针遍历数组元素，慢指针指向非val元素结束的位置。
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
效率：0ms，击败100.00%
977. 有序数组的平方
思路1：O(nlogn)：使用库函数sort
其实直接使用库函数效率也不低啊hhh
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
new_arr = []
for num in nums:
new_arr.append(num * num)
new_arr.sort()
return new_arr
效率：7ms，击败88.81%
因为sort()的时间复杂度是O(n log n)，所以整体时间复杂度是 O(n) + O(n log n) = O(n log n)
思路2：O(n)：双指针
因为原数组存在一个特性，就是本身就是非递减顺序排列的。
那么平方后的新数组的最大值一定存在在原数组的两端（要么最左端最小值，要么最左端最大值）。而从原数组两端使用双指针向中间遍历，则就是新数组的最大值逐渐递减遍历。所以我们倒序填充新数组。
所以代码如下：
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left = 0
right = n-1
new_arr = [0] * n
# 倒序填充新数组
for i in range(n-1, -1, -1):
if abs(nums[left]) > abs(nums[right]):
new_arr[i] = nums[left] * nums[left]
left += 1
else:
new_arr[i] = nums[right] * nums[right]
right -= 1
return new_arr
效率：3ms，击败98.13%
209.长度最小的子数组
思路1：暴力解法
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
"""
暴力解法，外层i循环遍历数组的开始位置，内层j循环遍历结束位置。
"""
n = len(nums)
min_length = n+1
for i in range(n):
for j in range(i,n):
sums = sum(nums[i:j+1])
if sums >= target:
# 一旦遇到总和满足条件了，就说明当前位置最小长度的子数组找到了
min_length = min(min_length, j-i+1)
break
return min_length if min_length != (n+1) else 0
时间复杂度为O(n^2)，会超出时间限制。
思路2：维护前缀和
我们首先考虑一下维护前缀和的思路。
因为当i固定时，j从i开始逐步增加，每次计算sum(nums[i:j+1])，这其实是可以用前缀和或者累加的方式来优化的。比如，内层循环可以维护一个当前的和，每次j增加的时候，加上nums[j]，而不是每次都重新计算整个子数组的和。这样可以把内层循环的时间复杂度从O(n)降到O(1)，虽然整体还是O(n^2)
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
"""
暴力解法，外层i循环遍历数组的开始位置，内层j循环遍历结束位置。
"""
n = len(nums)
min_length = n+1
for i in range(n):
current_sum = 0
for j in range(i,n):
current_sum += nums[j]
if current_sum >= target:
# 一旦遇到总和满足条件了，就说明当前位置开始，最小长度的子数组找到了
min_length = min(min_length, j-i+1)
break
return min_length if min_length != (n+1) else 0
还是会超时，而这里又有两层循环，所以我们想到双指针来优化它。
思路3：双指针滑动窗口法
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
min_length = n+1
left = 0
current_sum = 0
for right in range(n):
current_sum += nums[right] # 扩展右边界
# 当总和满足条件时，尝试缩小左边界
while current_sum >= target:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1 # 左边界右移
return min_length if min_length != (n+1) else 0
为什么这里我们的for循环要遍历终止位置？而不是起始位置？
因为如果是起始位置的话，我们要找到答案，还是需要维护一个起始位置向后的遍历，那和暴力解法其实没有区别了。因为每个元素可能被访问不止两次
譬如对于nums[3]，起始位置j=0时，终止位置i指针向右遍历时会访问到它一次。然后起始位置j=1时，终止位置i指针向右遍历时会访问到它第二次。起始位置j=2时，终止位置i指针向右遍历时会访问到它第三次。
但是如果是终止位置的话，每个元素最多被访问到两次。
譬如对于nums[3]，第一次访问到他时是终止位置j向右拓展时j=3时。然后j就会停止不动了，左边界右移也不会访问到它。之后j=4以及j继续遍历时，因为左边界只会不断右移，所以也只可能访问它1次。
滑动窗口的维护：
- 右指针 right：遍历数组，逐步扩展窗口的右边界，累加元素和。
- 左指针 left：当窗口内元素和 current_sum >= target 时，尝试右移左边界，缩小窗口长度，同时更新最小长度。
时间复杂度 O(n)：每个元素最多被访问两次（被 left 和 right 各处理一次）。
效率：11ms，击败76.45%
59. 螺旋矩阵 II
这道题最重要的知识点就是，每转一圈会少2行，所以对于n个数字，n为偶数的话会转n/2圈，n为奇数的话会转n/2圈并多出最后一个数字。
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0] * n for _ in range(n)]
# 每转一圈会少2行。所以对于n个数字，n为偶数的话会转n/2圈，n为奇数的话会转n/2圈并多出最后一个数字。
# 对每条边实行左闭右开,start_x和start_y代表每一圈左上角的起始位置
start_x = start_y = 0
offset = 1
# offset控制每圈边界的缩小
count = 1
for _ in range(n//2):
# 处理上边
for j in range(start_y, n-offset):
matrix[start_x][j] = count
count += 1
# 处理右边
for i in range(start_x, n-offset):
matrix[i][n-offset] = count
count += 1
# 处理下边
for j in range(n-offset, start_y, -1):
matrix[n-offset][j] = count
count += 1
# 处理左边
for i in range(n-offset, start_x, -1):
matrix[i][start_y] = count
count +=1
offset += 1
start_x += 1
start_y += 1
if n%2:
matrix[n//2][n//2] = count
return matrix
效率：0ms，击败100.00%