代码随想录算法训练营第二天| 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;}}
}

---

解题思路：

滑动窗口是一种高效解决连续子数组问题的算法，特别适用于寻找满足特定条件的最小或最大子数组。该方法的核心思想是在遍历数组时维护一个窗口（即子数组），当窗口中的元素和满足目标条件时，缩小窗口的大小以尝试找到更小的子数组。

步骤：

1. 初始化两个指针 left 和 right，并使用一个变量 sum 来存储窗口内元素的和。
2. 当 right 指针向右扩展时，将 nums[right] 加入 sum，形成窗口。
3. 当窗口内的和大于等于目标 target 时，计算当前窗口长度，并尝试缩小窗口，直到窗口内的和小于 target。
4. 在每次窗口满足条件时更新最小子数组长度。

这种方法的时间复杂度为 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 的正方形矩阵。可以通过分层的方式，逐步填充矩阵的外圈，并不断收缩到内圈。

步骤：

1. 通过定义上下左右四个边界（即 startx、starty、offset），按顺时针方向依次填充每层的矩阵元素。
2. 每次循环都减少边界的范围，直到边界缩小到中心位置。
3. 如果矩阵的阶数 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 的格子，每个格子有一个整数表示该格子的价值。开发商希望找到一个方式将该土地划分为两部分，并使得这两部分的价值差最小。程序要求输出最小价值差。

解题思路

该问题可以通过逐步累积和的方式进行解决：

1. 首先，我们需要计算每行和每列的总价值，这样我们可以比较在每行或每列切分时的两部分价值差。
2. 对于每行累加求和 xp[i]，表示第 i 行的价值总和；对每列累加求和 yp[j]，表示第 j 列的价值总和。
3. 然后逐行和逐列累积行、列的总和，与整体价值总和的差值进行比较，得到最小的差值。

通过这种方法，我们可以通过不断尝试在不同位置切分土地，找到使得两部分价值差最小的位置。

代码实现

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();}
}