Day2 第一章 数组part02
滑动窗口
定义
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢。
首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。
与双指针的区别
双指针是关心两个点，首位的数
滑动窗口关心的是区间内的
停止条件及左右指针
外层循环的停止条件永远是「右指针走到头」，而不是左右指针都走到头。
右指针负责"遍历完所有可能性"，所以它走到头才停；
左指针只负责"优化当前窗口"，所以它跟着条件走，条件没了它就停。
左指针永远是被右指针"拖着走"的，绝不会自己跑到终点。
长度最小的子数组
题目
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。 示例： 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。思路
left right都在最左边，然后右指针往右搜索，直到窗口内的数满足条件，然后记录长度，则左窗口-1，并且记录下长度，直到不满足条件，然后右指针再往右搜索，往复直到右指针到达最优侧，结束。
代码
#（版本一）滑动窗口法 class Solution: def minSubArrayLen(self, s: int, nums: List[int]) -> int: l = len(nums) left = 0 right = 0 min_len = float('inf') cur_sum = 0 #当前的累加值 while right < l: cur_sum += nums[right] while cur_sum >= s: # 当前累加值大于目标值 min_len = min(min_len, right - left + 1) cur_sum -= nums[left] left += 1 right += 1 return min_len if min_len != float('inf') else 0注意点：
1. 他的赋值，学习一下：float('inf')
2. 最后一句是条件表达式：return min_len if min_len != float('inf') else 0
A if 条件 else B= "条件成立就取 A，不成立就取 B"
题目链接
209. 长度最小的子数组 - 力扣（LeetCode）
螺旋矩阵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]]: # 1. 初始化 n*n 矩阵和四个边界 matrix = [[0] * n for _ in range(n)] top, bottom, left, right = 0, n - 1, 0, n - 1 num = 1 # 当前要填入的数字 target = n * n # 总共需要填的数字个数 # 2. 只要还有数字没填完，就继续转圈 while num <= target: # ① 上边：从左到右 → for col in range(left, right + 1): matrix[top][col] = num num += 1 top += 1 # 上边界下移 # ② 右边：从上到下 ↓ for row in range(top, bottom + 1): matrix[row][right] = num num += 1 right -= 1 # 右边界左移 # ③ 下边：从右到左 ← for col in range(right, left - 1, -1): matrix[bottom][col] = num num += 1 bottom -= 1 # 下边界上移 # ④ 左边：从下到上 ↑ for row in range(bottom, top - 1, -1): matrix[row][left] = num num += 1 left += 1 # 左边界右移 return matrix题目链接
59. 螺旋矩阵 II - 力扣（LeetCode）
区间和
题目
58. 区间和（第九期模拟笔试） 题目描述 给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。 输入描述 第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b > = a），直至文件结束。 输出描述 输出每个指定区间内元素的总和。 输入示例 5 1 2 3 4 5 0 1 1 3 输出示例 3 9 提示信息 数据范围： 0 < n <= 100000就是先给一个数字，比如说5，那么数组就是[1, 2, 3, 4, 5]
然后再给一个区间，比如说0 1，那么就是从0到1，在比如说4 9，那么就是从4到9
思路
前缀和，用空间换时间，记录下每一次sum到值，比如说sum3就是前三个数和，sum10就是前10个数的和，那么我们求区间4 9，那就是sum10-sum4
代码
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 presum = 0 for i in range(n): presum += vec[i] p[i] = presum 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()两个学习的点
1. input函数改成，input = sys.stdin.read，然后注意， data = input().split()，有个括号
2. print函数，print('\n'.join(map(str, result)))，就是先map(str, result))，把int改成str，然后'\n'.join(map(str, result))，['3', '9']→'3\n9'
题目链接
58. 区间和（第九期模拟笔试）
开发商购买土地
题目
题目描述 在一个城市区域内，被划分成了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() 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) # 统计横向 horizontal = [0] * n for i in range(n): for j in range(m): horizontal[i] += vec[i][j] # 统计纵向 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(sum - 2 * horizontalCut)) verticalCut = 0 for j in range(m): verticalCut += vertical[j] result = min(result, abs(sum - 2 * verticalCut)) print(result) if __name__ == "__main__": main()题目链接
44. 开发商购买土地（第五期模拟笔试）
最后两道题：前缀和和区间和
核心本质
只要题目涉及“连续子数组/子矩阵的元素之和”，无论它是让你“查询”还是让你“枚举分割点”，底层数学原理都是前缀和。
什么时候使用
出现“和”，连续一段，子区间，连续重复查询，就可以想到前缀和
总结数组部分
数组经典题目
二分法
这道题目呢，考察数组的基本操作，思路很简单，但是通过率在简单题里并不高，不要轻敌。
可以使用暴力解法，通过这道题目，如果追求更优的算法，建议试一试用二分法，来解决这道题目
- 暴力解法时间复杂度：O(n)
- 二分法时间复杂度：O(logn)
在这道题目中我们讲到了循环不变量原则，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。
二分法是算法面试中的常考题，建议通过这道题目，锻炼自己手撕二分的能力。
双指针法
双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
- 暴力解法时间复杂度：O(n^2)
- 双指针时间复杂度：O(n)
这道题目迷惑了不少同学，纠结于数组中的元素为什么不能删除，主要是因为以下两点：
- 数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）。
- C++中vector和array的区别一定要弄清楚，vector的底层实现是array，封装后使用更友好。
双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。
滑动窗口
本题介绍了数组操作中的另一个重要思想：滑动窗口。
- 暴力解法时间复杂度：O(n^2)
- 滑动窗口时间复杂度：O(n)
本题中，主要要理解滑动窗口如何移动 窗口起始位置，达到动态更新窗口大小的，从而得出长度最小的符合条件的长度。
滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
如果没有接触过这一类的方法，很难想到类似的解题思路，滑动窗口方法还是很巧妙的。
模拟行为
模拟类的题目在数组中很常见，不涉及到什么算法，就是单纯的模拟，十分考察大家对代码的掌控能力。
在这道题目中，我们再一次介绍到了循环不变量原则，其实这也是写程序中的重要原则。
相信大家有遇到过这种情况： 感觉题目的边界调节超多，一波接着一波的判断，找边界，拆了东墙补西墙，好不容易运行通过了，代码写的十分冗余，毫无章法，其实真正解决题目的代码都是简洁的，或者有原则性的，大家可以在这道题目中体会到这一点。
前缀和
前缀和的思路其实很简单，但非常实用，如果没接触过的录友，也很难想到这个解法维度，所以 这是开阔思路 而难度又不高的好题。