209. 长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/
解题思路
思路1：暴力解法
通过两个for循环，找出所有的可能的区间，并比较出最小区间
思路2：滑动窗口
因为需要找出的是连续的一个子数组，所以可以模拟一个从左到右滑动的一个框（也可以看成是一个区间），框内是一个子数组，如果子数组的值大于等于target，且框的长度最小，则这个框里面的元素，就是目标子数组。
代码实现1：
public static int minSubArrayLen(int target, int[] nums) {
// 使用一个for循环，找出最小区间
int sum = 0;
int left = 0;
int rtn = Integer.MAX_VALUE; // 返回的最小区间长度
for (int right=0; right < nums.length; right++) {
// 滑动块向右扩展
sum += nums[right];
// 判断滑动框内是否有更小的，满足条件的区间
while(sum >= target) {
rtn = Math.min(rtn, right - left + 1);
sum -= nums[left++];
}
}
return rtn == Integer.MAX_VALUE ? 0 : rtn;
}
代码实现2:
public int minSubArrayLen(int target, int[] nums) {
// 定义一个滑动框
int sum = 0; // 滑动框内子数组的和
int rtn = 0; // 最小的子数组长度
int left = 0; // 表示滑动框最左的下标
int right = 0; // 表示滑动框最右的下标
while(true) {
// 如果框内的和小于target，则需要向右扩展
if (sum < target) {
// 判断条件，如果数组遍历结束，则跳出循环
if (right >= nums.length) {
break;
}
sum += nums[right++];
continue;
}
// 总和大于等于target时，判断最小长度
// 不需要加一，因为向右扩展时，右指针已经跳到下一个元素了
rtn = rtn == 0 ? right - left: Math.min(rtn, right - left);
// 总和大于target，则需要缩小滑动框
sum -= nums[left++];
}
return rtn;
}
59. 螺旋矩阵
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/description/
解题思路
这道题没有简便方法，只有模拟数字填充的过程。
思路1：贪吃蛇法
螺旋矩阵就像贪吃蛇的房间，遇到墙就得换个方向。从0,0位置开始，向右开始填充，如果右边碰到墙了，则向下填充，向下碰到墙了，向左填充，向左碰到墙了，在向上；以此类推，这里的碰到墙就是满足下面一个条件：
1、坐标等于n-1
2、坐标等于0
3、下一个空格已有值了（Java初始化的数组默认填充的是0）
代码如下：
public static int[][] generateMatrix0(int n) {
int square = n * n;
// 创建一个矩阵
int[][] rtn = new int[n][n];
// 设置一个方向 0：右，1：下，2：左，3：上
int direction = 0;
// 设置当前数字所在坐标
int x = 0; // 横坐标
int y = 0; // 纵坐标
for (int i = 1; i <= square; i++) {
rtn[y][x] = i;
// 判断下一步怎么走
if (direction == 0) {
// 向右，如果到头了，则转向下
if (x + 1 == n || rtn[y][x+1] != 0) {
direction = 1;
y++;
} else {
x++;
}
} else if (direction == 1) {
// 向下，如果到头了，则转向左
if (y + 1 == n || rtn[y+1][x] != 0) {
direction = 2;
x--;
} else {
y++;
}
} else if (direction == 2) {
// 向左到头了，则向上
if (x == 0 || rtn[y][x-1] != 0) {
direction = 3;
y--;
} else {
x--;
}
} else {
// 向上，到头了则向右
if (rtn[y-1][x] != 0) {
direction = 0;
x++;
} else {
y--;
}
}
}
return rtn;
}
思路2：画圈法
螺旋矩阵可以看成画圈，先把外面的圈填充完，再填充里面的。要注意的是，行和列的空格数量是一致的，术语话就是要坚持循环不变量原则，处理每一行或每一列，都是左闭右开区间
示例图如下：
代码实现：
public static int[][] generateMatrix(int n) {
int[][] rtn = new int[n][n];
int loop = 1; // 记录当前是第几圈
int indexX = 0, indexY = 0; // 记录下一个圈的起始坐标
int count = 1; // 记录矩阵值
int i=0,j=0; // 记录当前放入值的坐标
// 每行都是左闭右开区间
// n/2 是多少就可以有几个圈
while(loop <= n / 2) {
// 每次都是从起始位置开始
i = indexX;
j = indexY;
// 处理顶行
for (; i < n - loop; i++) {
rtn[j][i] = count++;
}
// 处理最右列
for (; j<n-loop; j++) {
rtn[j][i] = count++;
}
// 处理下行
for (;i>indexX;i--) {
rtn[j][i] = count++;
}
// 处理左列
for (;j>indexY;j--) {
rtn[j][i] = count++;
}
// 进入下一圈
loop++;
indexX++;
indexY++;
}
// 如果是奇数，最后的一个位置在中心，需要特殊处理
if (n % 2 == 1) {
rtn[indexY][indexX] = count;
}
return rtn;
}
58. 区间和
题目链接：https://kamacoder.com/problempage.php?pid=1070
解题思路
前缀和
题目要求是获取一个数组，并返回指定区间数组元素的合。那用一个数组 sums 来存储前缀和，sums[i] 的值就表示从 0~i 的合，获取指定区间的合只需要用终止节点的前缀合减去起始节点前一个节点的合就可以了。
小提醒，题目内提交的Java代码，类名称必须是Main
代码实现：
import java.util.Scanner;
/**
* 区间和
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 获取n
int n = scanner.nextInt();
// 用于存储区间和
int[] sums = new int[n];
// 从控制器输入数据，并存储到区间和内
int sum = 0;
for (int i=0; i<n; i++) {
int num = scanner.nextInt();
sum += num;
sums[i] = sum;
}
// 获取区间，并输出和
while(scanner.hasNextInt()) {
int start = scanner.nextInt();
int end = scanner.nextInt();
if (start == 0) {
System.out.println(sums[end]);
} else {
System.out.println(sums[end] - sums[start-1]);
}
}
// 记得关闭输入
scanner.close();
}
}