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