前言
今天是算法训练营的第二天，现在明显觉得加入训练营是很有必要的，先前一个人孤军奋战刷题单时从来没有过像现在这么高的效率和驱动力，希望这股子能量可以持续到最后～
209.长度最小的子数组
题目链接：209. 长度最小的子数组
题目描述：
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
思路
这道题依然适用暴力，但力扣官方在测试用例里添加了一个用例使得暴力解法强制超时，除了暴力以外就是滑动窗口思想了。这边主要描述下我对滑动窗口的理解，滑动窗口是一个动态的变化过程，使用两个指针，一个记录窗口起始位置，一个记录窗口结束位置，在两者之间则在窗口当中，我们通过不断变化窗口两端位置最终得到我们想要的最佳效果。
暴力写法
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
result = float('inf')
size = len(nums)
sum1 = 0
temp = 1
for i in range(0, size):
sum1 = 0
temp = 1
sum1 += nums[i]
if sum1 >= target:
return temp
for j in range(i+1, size):
sum1 += nums[j]
temp += 1
if sum1 >= target:
if temp < result:
result = temp
if sum(nums) < target:
return 0
return result暴力写法没什么好说的，两个循环不断比较大小，我写法有点幼稚
滑动窗口写法
这里用j来标记窗口终止位置，并持续记录窗口内数值总和，一旦发现大于目标值就比较窗口大小是否小于目前最小值，并内收窗口起始位置。
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
result = float('inf')
sum1 = 0
i = 0
for j in range(0, len(nums)):
sum1 += nums[j]
while sum1 >= target:
result = min(result, j - i + 1)
sum1 -= nums[i]
i += 1
return result if result != float('inf') else 0在这里需要注意，虽然使用到了两个循环来完成目标，但这里的时间复杂度并不是O(n^2)，计算时间复杂度时看的是元素的操作次数，在这道题里只会操作两次，所以最后化简完是O(n)。
59.螺旋矩阵
题目链接：59. 螺旋矩阵 II
题目描述：
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路
这道题目似乎没有什么很好的特殊方法来解决，主要思路是通过模拟填数字的过程，填数字主要是重复经历四个阶段，先横向从左到右，再从最右侧从上到下，再从最下侧从右到左，再从最左侧从下到上，但是以上过程都有个特点：填数字的过程保持左闭右开，右为下一次操作的起始位置，我们需要做的是模拟这样的操作过程。
实现写法
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0] * n for _ in range(n)]
top = 0
bottom = n - 1
left = 0
right = n - 1
num = 1
while top <= bottom and left <= right:
#上面的从左往右
for i in range(left, right + 1):
matrix[top][i] = num
num += 1
top += 1
#右边的从上到下
for i in range(top, bottom + 1):
matrix[i][right] = num
num += 1
right -= 1
#下面的从右到左
for i in range(right, left - 1, -1):
matrix[bottom][i] = num
num += 1
bottom -= 1
#左边的从下到上
for i in range(bottom, top - 1, -1):
matrix[i][left] = num
num += 1
left += 1
return matrix58.区间和
题目链接：58.区间和
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3输出示例
3
9数据范围：
0 < n <= 100000
思路
这道题用到了数组常见思路：前缀和，刚看到这道题因为题目的ACM模式吓晕了，以前没怎么接触过，刚拿到手也很生疏。刚看到这道题我第一时间想到的依然是暴力解法，但是看到文档里有说暴力解法被卡，我选择文档里的前缀和做法。
前缀和思想主要是引入一个数组专门用来记录先前数值的总和，这样方便我们在每次需要提取数值和时不需要把每个数值再加一遍，大大提高效率，就之前刷题的经历来看，前缀和在解决数组计算问题时常用。
这道题一方面是巩固前缀和思想，另一方面更加拓展我对ACM 模式的空白。
前缀和写法
import sys
input = sys.stdin.read
def main():
data = input().split()
index = 0
n = int(data[index])
index += 1
p = [0] * n
vec = [0] * n
for i in range(n):
vec[i] = int(data[index + i])
presum = 0
for i in range(n):
presum += vec[i]
p[i] = presum
index += n
results = []
while index < len(data):
a = int(data[index])
b = int(data[index + 1])
index += 2
if a == 0:
sum_value = p[b]
else:
sum_value = p[b] - p[a - 1]
results.append(sum_value)
for result in results:
print(result)
if __name__ == "__main__":
main()44.开发商购买土地
题目链接：44.开发商购买土地
题目描述：
【题目描述】
在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。
为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分。
【输入描述】
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
输出描述
请输出一个整数，代表两个子区域内土地总价值之间的最小差距。
【输入示例】
3 3 1 2 3 2 1 3 1 2 3
【输出示例】
0
【提示信息】
如果将区域按照如下方式划分：
1 2 | 3 2 1 | 3 1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。
【数据范围】：
- 1 <= n, m <= 100；
- n 和 m 不同时为 1。
思路
这道题主要思想还是使用到前缀和，由于区域划分只能按横向或者纵向来划分，所以我们要做的就是分别求出横向划分时两个区域的总价值差和纵向划分时两个区域的总价值差。
在具体实现落地时，我们可以发现横向和纵向的实现逻辑几乎一致。
前缀和实现写法
import sys
input = sys.stdin.read
def main():
data = input().split()
index = 0
n = int(data[index])
index += 1
p = [0] * n
vec = [0] * n
for i in range(n):
vec[i] = int(data[index + i])
presum = 0
for i in range(n):
presum += vec[i]
p[i] = presum
index += n
results = []
while index < len(data):
a = int(data[index])
b = int(data[index + 1])
index += 2
if a == 0:
sum_value = p[b]
else:
sum_value = p[b] - p[a - 1]
results.append(sum_value)
for result in results:
print(result)
if __name__ == "__main__":
main()数组部分总结
在这一部分主要学习巩固了五种数组问题的解题方法分别是：
- 二分法
- 双指针法
- 滑动窗口
- 模拟行为
- 前缀和
二分法
首先是二分法，观察下来二分法的使用场景有一些特征：比如数组必须单调有序的，如果无序也得自己先排序后再使用。
二分法主要采用一种分而治之的思想，把问题规模减半非常巧妙。这样一来处理效率较高，时间复杂度仅为O(log n)。
在使用二分法时需要时刻注意下左闭右闭和左闭右开两种状况的写法区别。
双指针法
双指针法是我觉得这个章节里最巧妙的一种思想，通过快慢指针来完成两个循环的工作，这样的操作可以非常有效的将原本暴力解法的O(n^2)降低到O(n)。
以目前的认知，我觉得双指针的使用场景主要是查找、去重和子数组的相关问题，总体来说非常巧妙，这里给到夯。
滑动窗口
滑动窗口思想同样也很有意思，我觉得滑动窗口和双指针极其相似，两者区别在于：双指针法是两个点，而滑动窗口是这两个点连成线。
滑动窗口将视角锁定在一个窗口序列里，而非处理整个序列，这样做将效率显著增高，依然是将原本暴力的O(n^2)降低到O(n)。
模拟行为
模拟行为这边用到的例题很有意思，虽然模拟行为并没有涉及什么具体的算法，但是思考题目的过程需要引导自己代入计算机的处理过程，这种操作符合之前了解到的计算思维哲学，但人脑终究是人脑如果题目复杂度提高，可能模拟起来就会变得恶心很多。
前缀和
前缀和的使用很常见了，前缀和尤其适合用来解决需要大量计算子数组或者子序列和的问题，前缀和主要是通过一次扫描将所有子数组和预先保存在一个前缀和数组中方便后续使用，这样的操作有点空间换时间。
总体来说前缀和思想非常巧妙实用～
