--------------------------------------------------209.长度最小的子数组------------------------------------------------------------------------------------题目建议： 本题关键在于理解滑动窗口，这个滑动窗口看文字讲解 还挺难理解的，建议大家先看视频讲解。 拓展题目可以先不做。
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
暴力解法和滑动窗口对应
暴力解法先确定起始位置的循环 滑动窗口确定结束位置的循环
错误解法
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int slow = 0, sum = 0;
int minSubL = nums.length;
for(int fast = 0; fast < nums.length; fast ++){
//fast的范围
sum += nums[fast];
if(sum >= target){
while(sum - nums[slow] >= target){
slow ++;
}
int subL = fast - slow + 1;
minSubL = Math.min(minSubL, subL);
}
}
if(minSubL == nums.length){
return 0;
}else{
return minSubL;
}
}
}
问题：未更新sum，而且无论如何找到了 slow都应该往前走
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int slow = 0, sum = 0;
int minSubL = nums.length;
for(int fast = 0; fast < nums.length; fast ++){
//fast的范围
sum += nums[fast];
while(sum >= target){
int subL = fast - slow + 1;
minSubL = Math.min(minSubL, subL);
sum = sum - nums[slow];
slow ++;
}
}
if(minSubL == nums.length){
return 0;
}else{
return minSubL;
}
}
}
错误实例：
target =
15
nums =
[1,2,3,4,5]
添加到测试用例
输出
0
预期结果
5
原因： 不够大int minSubL = nums.length;加一
更改结果：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int slow = 0, sum = 0;
int minSubL = nums.length + 1;
for(int fast = 0; fast < nums.length; fast ++){
//fast的范围
sum += nums[fast];
while(sum >= target){
int subL = fast - slow + 1;
minSubL = Math.min(minSubL, subL);
sum = sum - nums[slow];
slow ++;
}
}
if(minSubL == nums.length+1){
return 0;
}else{
return minSubL;
}
}
}
注意时间复杂度 每个元素进来时被操作一次 出去被操作一次 所以是O(2*N)即O(N)
-------------------------------------------------------------------59.螺旋矩阵II------------------------------------------------------------------------------
题目建议： 本题关键还是在转圈的逻辑，在二分搜索中提到的区间定义，在这里又用上了。
题目链接：https://leetcoxde.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
注意 i 和 j有记录作用 定义在循环外 注意开区间
class Solution {
public int[][] generateMatrix(int n) {
int startx = 0, starty = 0;
int count = 1, offset =1;
int i, j, q =0;
int[][] reslut = new int[n][n];//初始化写法 动态
while(q < n/2){
for(j = starty; j < n - offset; j ++){
reslut[startx][j] = count++;
}
for(i = startx; i < n - offset; i ++){
reslut[i][j] = count++;
}
for(; j > 0; j --){
reslut[i][j] = count++;
}
for(; i > 0; i --){
reslut[i][j] = count++;
}
}
if (n % 2 != 0) {
reslut[n/2][n/2] = count++;
}
return reslut;
}
}
改进一：
class Solution {
public int[][] generateMatrix(int n) {
int startx = 0, starty = 0;
int count = 1, offset =1;
int i, j, q =0;
int[][] reslut = new int[n][n];
while(q < n/2){
for(j = starty; j < n - offset; j ++){
reslut[startx][j] = count++;
}
for(i = startx; i < n - offset; i ++){
reslut[i][j] = count++;
}
for(; j > startx; j --){
reslut[i][j] = count++;
}
for(; i > starty; i --){
reslut[i][j] = count++;
}
startx ++;
starty ++;
}
if (n % 2 != 0) {
reslut[n/2][n/2] = count++;
}
return reslut;
}
}
改进2：
class Solution {
public int[][] generateMatrix(int n) {
int startx = 0, starty = 0;
int count = 1, offset =1;
int i, j, q =0;
int[][] reslut = new int[n][n];
while(q < n/2){
for(j = starty; j < n - offset; j ++){
reslut[startx][j] = count++;
}
for(i = startx; i < n - offset; i ++){
reslut[i][j] = count++;
}
for(; j > starty; j --){
reslut[i][j] = count++;
}
for(; i > startx; i --){
reslut[i][j] = count++;
}
startx ++;
starty ++;
offset ++;
}
if (n % 2 != 0) {
reslut[n/2][n/2] = count++;
}
return reslut;
}
}
改进3：
q ++;
正确版本：
class Solution {
public int[][] generateMatrix(int n) {
int startx = 0, starty = 0;
int count = 1, offset =1;
int i, j, q =0;
int[][] reslut = new int[n][n];
while(q < n/2){
for(j = starty; j < n - offset; j ++){
reslut[startx][j] = count++;
}
for(i = startx; i < n - offset; i ++){
reslut[i][j] = count++;
}
for(; j > starty; j --){
reslut[i][j] = count++;
}
for(; i > startx; i --){
reslut[i][j] = count++;
}
startx ++;
starty ++;
offset ++;
q ++;
}
if (n % 2 != 0) {
reslut[n/2][n/2] = count++;
}
return reslut;
}
}
区间和
前缀和是一种思维巧妙很实用 而且 很有容易理解的一种算法思想，大家可以体会一下
文章讲解：https://www.programmercarl.com/kamacoder/0058.%E5%8C%BA%E9%97%B4%E5%92%8C.html
开发商购买土地
