IhaveBB 
匿名 
IhaveBB AI摘要：文章介绍了四个算法问题：使用滑动窗口求长度最小的子数组，利用前缀和计算区间和，通过边界控制生成螺旋矩阵II，以及基于前缀和思想寻找土地划分的最小价值差。
Powered by AISummary.
长度最小的子数组
题目
给定一个含有 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
思路：
刚看到这道题时，最先想到的仍是暴力算法
使用两个for循环，枚举所有连续子数组，再从中找出满足条件的最小长度。
后面学到可以用双指针解决，双指针本质上是在用两个指针模拟嵌套循环，但通过控制指针的移动方向，把重复计算压缩掉。
接下来关键的问题是：
哪个指针负责从头遍历到尾？
如果让左指针作为“主循环指针”，那么右指针仍然需要为每一个左指针去遍历后续的所有元素，这本质上和暴力解法并没有区别，时间复杂度依旧是平方级。
因此，只能让右指针作为主指针，从左到右遍历整个数组。
当右指针向右移动时，不断累加当前窗口内的元素和。一旦窗口内的和第一次达到或超过目标值 s，说明当前区间已经是一个可行解。
这时，尝试移动左指针向右收缩窗口：
- 左指针每右移一步，就需要先从窗口和中减去对应的元素
- 同时计算当前窗口的长度，并更新最小值
- 只要窗口内的和仍然满足
s，就继续收缩 - 一旦不满足条件，就停止收缩，继续移动右指针
这样做的核心在于：
右指针负责找到“可行解”，左指针负责把“可行解”压缩到最短。
在收缩窗口的过程中，每成功移动一次左指针，都需要完成两件事：
- 缩小窗口内的数值范围（更新窗口和）
- 计算当前窗口长度，并更新最小值（
right - left + 1）
由于左右指针都只会单调向右移动，每个元素最多被加入和移除一次，因此整体时间复杂度最终被优化到了 O(n) 。
题解：
♾️ sql 代码:class Solution {
public int minSubArrayLen(int target, int[] nums) {
int arr_length = nums.length;
int result_length = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
for(int right = 0; right < arr_length; right++){
sum += nums[right];
//当右指针左边的数值大于目标值时候缩小窗口
while(sum >= target){
//进入while条件说明满足，先更新结果
result_length = Math.min(result_length, right - left + 1);
//缩小窗口
sum -= nums[left];
left++;
}
}
return result_length == Integer.MAX_VALUE ? 0 : result_length;
}
}区间和
题目
https://kamacoder.com/problempage.php?pid=1070
题目描述
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b （b \> \= a），直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
♾️ text 代码:5
1
2
3
4
5
0 1
1 3输出示例
♾️ text 代码:3
9提示信息
数据范围：
0 \< n \<\= 100000
思路
首先看到这一题，用暴力解法来看的话呢，也就是数组中收集出数据后，对于每次计算，进行一次a到b的累加操作，虽不算慢，但在极端场景下仍是会出现超时，但也不算优雅，因此了解到了区间和
sum[i] 表示从数组 arr[0] 到 arr[i] 的累加和，区间 [a, b] 的和就可以快速计算为：
sum[b] - (a == 0 ? 0 : sum[a - 1])题解
♾️ sql 代码:import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int arr_length = sc.nextInt();
int[] arr = new int[arr_length];
int[] sum = new int[arr_length];
int pre = 0;
for (int i = 0; i < arr_length; i++) {
arr[i] = sc.nextInt();
if (i == 0) {
sum[i] = arr[i];
} else {
sum[i] = sum[i - 1] + arr[i];
}
}
while (sc.hasNext()) {
int a = sc.nextInt();
int b = sc.nextInt();
int result = sum[b] - (a > 0 ? sum[a - 1] : 0);
System.out.println(result);
}
sc.close();
}
}59.螺旋矩阵II
题目
给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
思路
这道题的核心并不在于算法复杂度，而在于边界控制是否清晰。
只要边界一旦混乱，就很容易出现覆盖或重复填充的问题。
整体思路可以拆解为两个关键点：
第一，如何保证每一圈只被填充一次，不发生覆盖；第二，如何在完成一圈后，正确地向内收缩边界。
为了避免元素被重复覆盖，在每条边的填充中，刻意保留拐角元素，把它们交给下一条边处理。
需要特别注意的是：
二维数组的本质是“行 + 列”，在填充时要始终保持“一维变化，另一维不动”，
当一整圈填充完成后，只需要同步收缩四个边界，进入下一圈。
题解
♾️ sql 代码:class Solution {
public int[][] generateMatrix(int n) {
int result[][] = new int[n][n];
int current = 1;
int top = 0;
int left = 0;
int right = n - 1;
int bottom = n - 1;
while(left <= right && top <= bottom){
//顶部
for(int i = left; i < right; i++){
result[top][i] = current;
current++;
}
//右侧
for(int i = top; i < bottom; i++){
result[i][bottom] = current;
current++;
}
//底部
for(int i = right; i > left; i--){
result[bottom][i] = current;
current++;
}
//左侧
for(int i = bottom; i > top; i--){
result[i][left] = current;
current++;
}
top++;
left++;
right--;
bottom--;
}
if(n % 2 != 0){
result[n/2][n/2] = current;
}
return result;
}
}开发商购买土地
题目
题目描述
在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。
现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。
然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。 为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。
注意：区块不可再分。
输入描述
第一行输入两个正整数，代表 n 和 m。
接下来的 n 行，每行输出 m 个正整数。
输出描述
请输出一个整数，代表两个子区域内土地总价值之间的最小差距。
输入示例
♾️ text 代码:3 3
1 2 3
2 1 3
1 2 3输出示例
♾️ text 代码:0提示信息
如果将区域按照如下方式划分：
1 2 | 3
2 1 | 3
1 2 | 3
两个子区域内土地总价值之间的最小差距可以达到 0。
数据范围：
1 \<\= n, m \<\= 100；
n 和 m 不同时为 1。
思路
这一题本质上是利用前缀和思想来寻找差值最小的分割方式。由于题目只允许进行一次横向或纵向切割，因此可以分别通过两次 for 循环，枚举按行划分和按列划分的所有可能切割位置，并在其中寻找最小差值。
在确定某一条分割线后，关键在于如何计算左右（或上下）两个区域的价值差。对于当前分割位置，可以将分割线一侧的区域视为前缀区域，另一侧视为剩余区域，二者的差值即为两部分区域总和之差的绝对值。
此时便可以引入前缀和的思想：若 sum[i] 表示从起始位置到第 i 行（或列）的前缀和，则分割线左侧（或上方）区域的总和为 sum[i]，右侧（或下方）区域的总和为 total - sum[i]，对应的差值计算公式为：
sum[i] - (total - sum[i])题解
♾️ sql 代码:import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] grid = new int[n][m];
int[] rowSum = new int[n];
int[] colSum = new int[m];
int total = 0;
// 读取数据 + 统计行和、列和、总和
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
grid[i][j] = sc.nextInt();
rowSum[i] += grid[i][j];
colSum[j] += grid[i][j];
total += grid[i][j];
}
}
int ans = Integer.MAX_VALUE;
// 横向切割
int prefix = 0;
for (int i = 0; i < n - 1; i++) { // 不能切在最后一行
prefix += rowSum[i];
int diff = Math.abs(prefix - (total - prefix));
ans = Math.min(ans, diff);
}
// 纵向切割
prefix = 0;
for (int j = 0; j < m - 1; j++) { // 不能切在最后一列
prefix += colSum[j];
int diff = Math.abs(prefix - (total - prefix));
ans = Math.min(ans, diff);
}
System.out.println(ans);
}
}
博主
IhaveBB👍
💖
💯
💦
😄
🪙
博主
IhaveBB👍
💖
💯
💦
😄
🪙