【LeetCode---209】长度最小的子数组---滑动窗口

声明：跟着Carl哥学的，欢迎关注代码随想录。

地址：https://www.programmercarl.com/

1、题干

2、滑动窗口思想

• 滑动窗口就是不断调节子序列的起始位置和终止位置，从而找到我们想要的结果。

• 在调节子序列的起始位置和终止位置的时候，需要我们根据具体的题干来加以判断。

• 图示

  

3、滑动窗口需要确定的点

• 窗口内是什么？
• 如何移动窗口的起始位置？
• 如何移动窗口的结束位置？
  窗口就是满足其和>=s的长度最小的连续子数组
  如果当前窗口的值大于s了，窗口就该向前移动了，也就是缩小了窗口，这个窗口内的值的和变小。也就是这个窗口的起始位置向右移动一个单元。
  窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

4、Java代码实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //这里的初始值设置的小技巧
        int result = Integer.MAX_VALUE;
        int sum = 0;//滑动窗口的数值之和
        int i = 0;//滑动窗口的起始位置
        int subLength = 0;//滑动窗口的长度
        for (int j=0;j < nums.length;j++){
            sum += nums[j];
            //注意这里要使用while，每次更新i的位置
            while(sum >= target){
                subLength = (j - i + 1);//取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i];//窗口移动之后，总体的值变小，减去最左边的那个值。
                i++;//窗口缩小
            }
        }
        
        //如果没有符合条件的就返回0
        return result == Integer.MAX_VALUE ? 0 :result;
    }
}

时间复杂度还是O(n)，主要看每一个元素被操作的次数，每个元素在滑动窗口进来后操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是2n，也就是O(n)。