代码随想录算法训练营第二天| 209.长度最小的子数组 59.螺旋矩阵II 区间和 开发商购买土地
209. 长度最小的子数组
题目：
给定一个包含正整数的数组 nums 和一个正整数 target ，找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
示例 1：
- 输入:
target = 7,nums = [2,3,1,2,4,3] - 输出:
2 - 解释: 子数组
[4,3]是该条件下的长度最小的子数组。
示例 2：
- 输入:
target = 4,nums = [1,4,4] - 输出:
1
示例 3：
- 输入:
target = 11,nums = [1,1,1,1,1,1,1,1] - 输出:
0
提示：
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
进阶：
如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n log(n)) 时间复杂度的解法。
暴力解法：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = nums.length + 1;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum = 0;
for (int j = i; j < nums.length; j++) {
sum = sum + nums[j];
if (sum >= target && result > j - i + 1) {
result = j - i + 1;
}
}
}
if (result == nums.length + 1) {
return 0;
} else {
return result;
}
}
}
滑动窗口解法：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = nums.length + 1;
int sum = 0;
int left = 0;
for (int i = 0; i < nums.length; i++) {
sum = sum + nums[i];
while (sum >= target) {
if (result > i - left + 1) {
result = i - left + 1;
}
sum = sum - nums[left];
left++;
}
}
if (result == nums.length + 1) {
return 0;
} else {
return result;
}
}
}
解题思路：
滑动窗口是一种高效解决连续子数组问题的算法，特别适用于寻找满足特定条件的最小或最大子数组。该方法的核心思想是在遍历数组时维护一个窗口（即子数组），当窗口中的元素和满足目标条件时，缩小窗口的大小以尝试找到更小的子数组。
步骤：
- 初始化两个指针
left和right，并使用一个变量sum来存储窗口内元素的和。 - 当
right指针向右扩展时，将nums[right]加入sum，形成窗口。 - 当窗口内的和大于等于目标
target时，计算当前窗口长度，并尝试缩小窗口，直到窗口内的和小于target。 - 在每次窗口满足条件时更新最小子数组长度。
这种方法的时间复杂度为 O(n)，因为每个元素在遍历过程中最多只会被访问两次。
59. 螺旋矩阵 II
题目：
给你一个正整数 n ，生成一个包含 1 到 n^2 的所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵。
示例：
- 输入:
n = 3 - 输出:
[
[1, 2, 3],
[8, 9, 4],
[7, 6, 5]
]
代码：
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int startx = 0;
int starty = 0;
int loop = 1;
int count = 1;
int offset = 1;
int i, j;
while (loop <= n / 2) {
for (j = starty; j < n - offset; j++) {
result[startx][j] = count;
count++;
}
for (i = startx; i < n - offset; i++) {
result[i][n - offset] = count;
count++;
}
for (j = n - offset; j > startx; j--) {
result[n - offset][j] = count;
count++;
}
for (i = n - offset; i > starty; i--) {
result[i][starty] = count;
count++;
}
startx++;
starty++;
offset++;
loop++;
}
if (n % 2 == 1) {
result[startx][starty] = count;
}
return result;
}
}
解题思路：
螺旋矩阵是一个典型的二维数组遍历问题，要求我们按照顺时针的顺序填充一个 n x n 的正方形矩阵。可以通过分层的方式，逐步填充矩阵的外圈，并不断收缩到内圈。
步骤：
- 通过定义上下左右四个边界（即
startx、starty、offset），按顺时针方向依次填充每层的矩阵元素。 - 每次循环都减少边界的范围，直到边界缩小到中心位置。
- 如果矩阵的阶数
n为奇数，最后剩下中心位置需要单独处理。
这是一种逐步推进的方式，按照顺时针方向填充矩阵，每次循环都会将一圈元素填满。
区间和问题
题目描述
给定一个长度为 n 的整数数组，要求计算多个区间的和。每次查询会给出两个整数 a 和 b，表示区间 [a, b]，程序需返回该区间内的元素之和。
解题思路
这个问题的核心在于如何高效计算多个区间的和。我们可以通过前缀和技巧来快速处理每次的查询。前缀和数组 p[i] 表示从数组的第一个元素到第 i 个元素的累加和。这样，对于任意区间 [a, b]，其区间和可以通过前缀和数组快速计算：
- 如果
a == 0，则区间和为p[b]，即直接得到从第 0 到第b元素的累积和。 - 如果
a > 0，则区间和为p[b] - p[a-1]，即减去a之前的累积和部分。
这种方法将每次查询的时间复杂度从 O(n) 降低到了 O(1)，大大提高了性能。
代码实现
import java.util.Scanner;
public class ArraySum {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt(); // 读取数组长度
int[] vec = new int[n]; // 原始数组
int[] p = new int[n]; // 前缀和数组
int presum = 0; // 累积和变量
// 构建前缀和数组
for(int i = 0; i < n; i++) {
vec[i] = input.nextInt(); // 读取数组元素
presum += vec[i];
p[i] = presum;
}
// 处理多次区间和查询
while(input.hasNextInt()) {
int a = input.nextInt(); // 起始位置
int b = input.nextInt(); // 结束位置
int sum = 0;
// 通过前缀和计算区间和
if (a == 0) {
sum = p[b];
} else {
sum = p[b] - p[a - 1];
}
// 输出结果
System.out.println(sum);
}
input.close();
}
}
开发商购买土地问题
题目描述
开发商计划购买一块矩形土地，土地被分为 m * n 的格子，每个格子有一个整数表示该格子的价值。开发商希望找到一个方式将该土地划分为两部分，并使得这两部分的价值差最小。程序要求输出最小价值差。
解题思路
该问题可以通过逐步累积和的方式进行解决：
- 首先，我们需要计算每行和每列的总价值，这样我们可以比较在每行或每列切分时的两部分价值差。
- 对于每行累加求和
xp[i]，表示第i行的价值总和；对每列累加求和yp[j]，表示第j列的价值总和。 - 然后逐行和逐列累积行、列的总和，与整体价值总和的差值进行比较，得到最小的差值。
通过这种方法，我们可以通过不断尝试在不同位置切分土地，找到使得两部分价值差最小的位置。
代码实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int m = input.nextInt(); // 行数
int n = input.nextInt(); // 列数
int[][] vec = new int[m][n]; // 土地价值矩阵
int[] xp = new int[m]; // 每行累积价值
int[] yp = new int[n]; // 每列累积价值
int sum = 0; // 总价值
int presum = 0;
// 计算每行的累积价值
for(int i = 0; i < m; i++) {
presum = 0;
for (int j = 0; j < n; j++) {
vec[i][j] = input.nextInt();
sum += vec[i][j]; // 总价值
presum += vec[i][j]; // 当前行累积价值
}
xp[i] = presum; // 保存当前行的累积价值
}
// 计算每列的累积价值
for (int j = 0; j < n; j++) {
presum = 0;
for (int i = 0; i < m; i++) {
presum += vec[i][j]; // 当前列累积价值
}
yp[j] = presum; // 保存当前列的累积价值
}
int xsum = 0;
int result = Integer.MAX_VALUE;
// 找出最小行切割差值
for (int i = 0; i < m; i++) {
xsum += xp[i];
result = Math.min(result, Math.abs(sum - 2 * xsum));
}
int ysum = 0;
// 找出最小列切割差值
for (int j = 0; j < n; j++) {
ysum += yp[j];
result = Math.min(result, Math.abs(sum - 2 * ysum));
}
// 输出结果
System.out.println(result);
input.close();
}
}