继续每天补一个，最好能加快进度赶上正常的TAT，可惜基础不够牢，边学边做
滑动窗口和双指针的条件，包括滑动窗口的移动要求要清楚
209.长度最小的子数组
题目描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的子数组[nums_l, nums_(l+1), ..., nums_(r-1), nums_r]，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路整理：
- 双指针法
利用sum计算总和，比较和target的大小，没超过target，则右指针继续移动，超过target，则左指针移动收缩
class Solution(object):
def minSubArrayLen(self, target, nums):
"""
:type target: int
:type nums: List[int]
:rtype: int
"""
left, sums = 0, 0
minlen = float('inf')
for right in range(len(nums)):
sums += nums[right]
while sums >= target:
# 用判断条件来控制left移动
minlen = min(minlen,right - left + 1) # 确保right指针已经指向了下个元素
sums -= nums[left]
left += 1
return minlen if minlen != float('inf') else 0
2.暴力法
暴力法相当于使用两层for循环，第一层取不同的数组起点，第二层取不同的数组终点，来求解最符合要求的数组，比较麻烦。
59.螺旋矩阵II
题目：
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思路整理：
- 双循环：我理解的核心是两个，一个是保证每次排列边的时候计算法则要保持一致，放置四条边时个数之类的保持一致，不然算法计算上会有可能产生冲突；二是第一层循环采用的是
offset，通过n - offset来控制每层循环缩小，最后再判断为奇数的情况看是否需要填充最后一个数。
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
nums = [[0] * n for _ in range(n)]
startx, starty = 0, 0 # 定义起始点
loop, mid = n // 2, n // 2
count = 1
for offset in range(1, loop + 1):
# 从左到右（左闭右开）
for i in range(starty, n - offset):
nums[startx][i] = count
count += 1
# 从上到下（上闭下开）
for i in range(startx, n-offset):
nums[i][n - offset] = count
count += 1
# 从右到左（右闭左开），注意方向
for i in range(n - offset, starty, -1):
nums[n - offset][i] = count
count += 1
# 从下到上（下闭上开），注意方向
for i in range(n - offset, startx, -1):
nums[i][starty] = count
count += 1
startx += 1
starty += 1
if n % 2 != 0:
nums[mid][mid] = count
return nums
- 定义四个边界：
分别对上下左右四个点的位置进行定义，这样条件从正方形框逐步缩小变成了每条边的指针位置，优势是不用单独考虑中间那个位置
class Solution(object):
def generateMatrix(self, n):
if n <= 0:
return []
# 初始化 n x n 矩阵
matrix = [[0]*n for _ in range(n)]
# 初始化边界和起始值
top, bottom, left, right = 0, n-1, 0, 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 matrix
区间和
题目：
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
思路整理：
通过利用p存储累计和，读取a和b时通过p(b) - p(a - 1)获得该区间和。
import sys
input = sys.stdin.read
def main():
data = input().split()
index = 0
n = int(data[index])
index += 1
vec = []
for i in range(n):
vec.append(int(data[index + i]))
index += n
p = [0] * n
count = 0
for v in range(n):
count += vec[v]
p[v] = count
results = []
while index < len(data):
a = int(data[index]) # 注意如何提取的a和b
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()
开发商购买土地
题目描述：
在一个城市区域内，被划分成了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。
思路整理：
分别计算每一行和每一列的和，类似前缀和的思路来比较，如果两块土地差距最小，啧单边的土地价值应该尽可能接近总和的一半。
def main():
import sys
input = sys.stdin.read
data = input().split()
n,m = int(data[0]),int(data[1])
vec = []
index = 2
horizontal = []
for i in range(n):
row = []
sums = 0
for j in range(m):
num = int(data[index])
index += 1
sums += num
row.append(num)
vec.append(row)
horizontal.append(sums)
total_sum = sum(horizontal)
vertical = [0] * m
for j in range(m):
for i in range(n):
vertical[j] += vec[i][j]
result = float('inf')
horizontalCut = 0
for i in range(n):
horizontalCut += horizontal[i]
result = min(result, abs(total_sum - 2*horizontalCut))
verticalCut = 0
for j in range(m):
verticalCut += vertical[j]
result = min(result, abs(total_sum - 2*verticalCut))
print(result)
if __name__ == "__main__":
main()
官方还提供了一个方案，在计算完行列结果即开始进行比较，对整个过程略微优化。
def main():
import sys
input = sys.stdin.read
data = input().split()
idx = 0
n = int(data[idx])
idx += 1
m = int(data[idx])
idx += 1
sum = 0
vec = []
for i in range(n):
row = []
for j in range(m):
num = int(data[idx])
idx += 1
row.append(num)
sum += num
vec.append(row)
result = float('inf')
count = 0
# 行切分
for i in range(n):
for j in range(m):
count += vec[i][j]
# 遍历到行末尾时候开始统计
if j == m - 1:
result = min(result, abs(sum - 2 * count))
count = 0
# 列切分
for j in range(m):
for i in range(n):
count += vec[i][j]
# 遍历到列末尾时候开始统计
if i == n - 1:
result = min(result, abs(sum - 2 * count))
print(result)
if __name__ == "__main__":
main()
