当前位置：首页 > news >正文

Day2 第一章数组part02

news 2026/7/5 14:29:55

滑动窗口

定义

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们想要的结果。

在暴力解法中，是一个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()