209. 长度最小的子数组

#算法/滑动窗口

209. 长度最小的子数组

题目链接
 代码随想录

分析

注意，我们只需要分析长度最小子数组的长度，只需要返回这个长度数字即可：用一个数字来表示最小长度，然后有更小的就更新它，最后返回这个数字即可。

其实代码随想录里的题解说这是滑动窗口的方法，其实我觉得本质上还是双指针法，而且代码随想录里的写法太复杂了，不利于记忆，所以这里就采用我自己的写法。

如何找到符合要求的子数组呢？
从慢指针到快指针的子数组 [slow,fast] 为当前子数组

如果子数组的元素和小于指定值，就移动快指针，
如果子数组的元素和大于等于指定值，就移动慢指针，并更新子数组长度。
什么时候跳出循环呢？当子数组的元素和小于指定值，需要移动快指针，而快指针已经到数组的最后一个元素的时候，就可以直接退出了（这是所有滑动窗题型都通用的条件）。为什么没有必要考虑慢指针呢？因为移动慢指针只会让子数组的和变小，也就是说再迭代下去，也没有让子数组的元素再次大于 target 的可能了，此时就可以退出循环了。
而且因为我们是求最小值，所以是在移动慢指针的时候移动更新结果。
这种方式就是像毛毛虫走路一样，前进一截，然后从后面缩回来一截，再前进一截，再从后面缩回来一截，因为我们要找的是连续的几个元素组成的子数组（算法方法总结#子集合、子序列和子数组的区别），所以只要有符合要求的子数组，一定会被这种方式扫描到。
用滑动窗口法，总共就三步：
什么时候移动快指针
什么时候移动慢指针
什么时候跳出循环
然后是在移动快指针的时候更新结果还是在移动慢指针的时候更新结果取决于你想用滑动窗口求最大值还是最小值，求最大值就在移动快指针的时候更新结果，求最小值就在移动慢指针的时候更新结果。
写算法题，我们首先要明确我们声明的每个变量的意义，根据我们对变量的定义，赋予初始值。然后根据我们对变量的定义来制定判断条件
确定算法复杂度：
根据复杂度#如何正确估算时间复杂度呢？
确定输入规模，假设输入规模为 n，也就是数组的大小为 n，
基本操作为循环
确定递推公式：递推公式不明显，快指针遍历一次整个数组是 n，慢指针又遍历一次，又是 n，因此可以确定循环的次数最多为 2n，
因此复杂度最多为 $O (2 n)$ ，经过化简，可得到复杂度为 $O (n)$
滑动窗口的时间复杂度为 $O (n)$ 。
此题的时间复杂度为 $O (n)$ 。

这个题我第二次做的时候很容易就想到思路，但是写代码居然花了 20 多分钟。可见解题的熟练度也是相当重要的。
第三次做的时候，依然花了 20 多分钟，god damn it。

解题

public int minSubArrayLen(int target, int[] nums) {
	// 默认给一个值，第一次更新的时候，只要实际值小于这个值就行，可以用 Integer.MAX_VALUE ，不过用 nums.length+1 就够了
    int maxLength = nums.length+1;
    int subLength = maxLength;
	// 快慢指针都从0开始，确定了子数组的左右边界[slow,fast]，
    int slow =0,fast =0;
    // 如果slow和fast都为0，相当于已经指定了一个子数组，这个子数组只有一个元素了，那就是nums[0]，所以此时子数组的元素和就是nums[0]
    int subSum = nums[0];
    for(;;){
        if(subSum<target){
            // 元素和小于指定值，移动快指针
            fast++;
			// 跳出循环的条件就是快指针到 nums.length
            if(fast>nums.length-1){
	            // fast 向右移动，肯定是子数组和不够大，此时再移动就超出，说明接下来不管再怎么移动slow指针都已经无法达到目标值，此时可以退出计算了
                break;
            }
            // 移动快指针之后，子数组元素和也要更新
            subSum+=nums[fast];
        }else{
            // 元素和大于等于指定值，开始计算子数组长度
            int nowLength = fast-slow+1;
            if(nowLength<subLength){
	            // 比上一次计算的值小，才更新
				subLength = nowLength;
            }
            // 注意先移除元素，再让slow增加
            subSum-=nums[slow];
            // 移动慢指针，
			slow++;
			// 这里有一个场景，就是当出现单个元素大于target的时候，最小子数组的长度就是1，那么此时就一定存在slow fast在这个元素上重合的场景
			// 此时 slow 向右移动，就会等于right+1 重合，不过下一个循环，fast自增，子数组有只包含一个元素了，也就是说 slow 比 right 大1这个是合理的
        }
    }
    // 没有找到满足要求的子数组，返回0
    if(subLength==maxLength){
        return 0;
    }
    // 返回 subLength
    return subLength;
}

209. 长度最小的子数组

分析

解题

相关题