代码随想录刷题day04|（数组篇）209.长度最小的子数组

一、数组理论基础

二、滑动窗口法

三、相关算法题目

四、相关知识点

1.三元运算符

2.表示MAX值的常量

3.全局变量和局部变量

五、心得

一、数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

代码随想录 (programmercarl.com)

特点：

1.下标从0开始，内存中地址空间是连续的

2.查询快，增删慢

3.二维数组中，行为第一索引，列为第二索引

4.一旦创建以后，长度不能发生变化

5.元素无法删除，只能被覆盖

二、滑动窗口法

数组操作中的另一个重要方法。

思想：用一个for循环，不断调节子序列的起始位置和终止位置，从而获得对应结果。

假设用变量 j 指向起始位置，那么终止位置要把后面每一个元素遍历一遍，得到以 j 指向的变量为开头的所有子序列的集合，然后选出满足目标的子序列，再得到长度最小值，这样的话，思想就和暴力法一样了。

所以，变量 j 应该指向终止位置，起始位置用动态移动的策略去移动，用一个for循环实现要求。

起始位置首先指向0索引位置，终止位置随着for循环依次往后移动，并依次计算起始位置到终止位置所包含子序列的数值之和，同时比较更新最小长度值，当子序列数值之和≥目标值时，起始位置开始依次向前移动，更新子序列数值之和，不断重复这个过程，直到子序列数值之和＜目标值，起始位置停止移动，终止位置继续随着for循环向后移动，不断重复这个过程。

其实内在原理依然是以每个元素为起始点，寻找满足目标值的子序列的集合，但滑动窗口是在每个元素为起始点的所有子序列集合中找到数值之和满足要求并且长度最小的那个子序列，比较各个最短长度，返回最终结果。

三、相关算法题目

209.长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

暴力法和滑动窗口法

暴力法（力扣上已超时）

思想：一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用双层for循环获得所有子序列的和，然后找到满足要求的子序列，并返回对应长度。

class Solution {public int minSubArrayLen(int target, int[] nums) {//暴力法 双层for循环 已超时int subL = 0; //子序列的长度int result = Integer.MAX_VALUE; //最终结果 返回的最小长度for(int i = 0;i < nums.length;i++){ //设置子序列起点为iint sum = 0; //子序列的数值之和for(int j = i;j < nums.length;j++){ //设置子序列终点为jsum = sum + nums[j]; if(sum >= target){ subL = j - i + 1; //取子序列长度result = result > subL ? subL: result;break; //因为是找长度最小 所以一旦符合条件就退出本次循环}}}return result == Integer.MAX_VALUE ? 0: result; //如果result没有被赋值的话就返回0 说明没有满足条件的子序列}
}

滑动窗口法（重点掌握）

class Solution {public int minSubArrayLen(int target, int[] nums) {//滑动窗口法（双指针法）int sum = 0;// 子序列的数值之和int i = 0;// 设置子序列的起点int subL = 0;// 子序列的长度int result = Integer.MAX_VALUE;//最终结果即最小长度for(int j = 0;j < nums.length;j++){sum = sum + nums[j];while(sum >= target){subL = j - i + 1;//取子序列长度result = result < subL ? result : subL;sum = sum - nums[i];i++; //起点往前滑动一个位置}}return result == Integer.MAX_VALUE ? 0 : result;//如果result没有被赋值的话就返回0 说明没有满足条件的子序列}
}

四、相关知识点

1.三元运算符

格式： 关系表达式？表达式1 ：表达式2 ；

计算关系表达式的值，如果为真，执行表达式1，如果为假，执行表达式2；

注意：该结果一定要被使用，要么赋值给一个变量，要么直接打印出来；

2.表示MAX值的常量

在java中，使用Integer.MAX_VALUE来表示一个非常大的整数，等同于 C++ 中的INT32_MAX。Integer.MAX_VALUE的值是2^31 - 1，即 2147483647。

3.全局变量和局部变量

全局变量：类的成员变量，定义在类中方法外部的变量，作用域是整个类；

局部变量：只在方法内定义的变量，作用域仅限于该方法；

result和sum（暴力法中）的区别

特性	result	sum
作用域	局部变量（方法级别）	局部变量（内层循环级别）
生命周期	整个方法执行过程	每次外层 i 循环从开始到结束之间
初始值	nums.length（初始化为数组长度）	0
更新频率	在满足条件时更新	在内层 j 循环中进行累加（一旦 i 循环进入下一次迭代，sum 会被重新赋值为0，其值不会跨越不同的 i 循环）