每日一题：长度最小的子数组

题目链接

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度 如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释： 子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入： target = 4, nums = [1,4,4]
输出： 1

示例 3：

输入： target = 11, nums = [1,1,1,1,1,1,1,1]
输出： 0

 

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

解题思路:(暴力解法)

这道题可以使用两个for循环解决

遍历数组，不断的寻找符合题目要求的最小子数组

代码:（JAVA实现）

public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;//最终结果
        int len = 0;//最小子数组的长度
        int sum = 0;//和
        for (int i = 0; i < nums.length;i++) {
            sum = 0;
            for (int j = i; j < nums.length;j++) {
                sum += nums[j];
                //当子数组和超过target时，更新len的长度
                if (sum >= target) {
                    len = j - i + 1;//取子数组的长度
                    //比较当前符合要求的子数组长度和上一个符合要求的子数组长度
                    //将更小的那个长度拿出来
                    if (result < len) {
                        result = result;
                    }else {
                        result = len;
                    }
                    break;
                }
            }
        }
        //如果result没有被赋值的话，返回0，说明没有找到符合条件的子数组
        if (result == Integer.MAX_VALUE) {
            return 0;
        }
        return result;
    }

复杂度分析:

• 时间复杂度:O(n^2)
• 空间复杂度:O(1)

提交结果

解题思路:(滑动窗口)

所谓滑动窗口，就是不断的移动子数组的起始位置和结束位置，从而找到我们想要的结果

滑动窗口其实可以理解为是双指针的一种，只不过比起双指针，它更像一个窗口在不停的移动，所以称它为滑动窗口

在本题中实现滑动窗口，主要有三点：

1. 窗口内是什么:满足和 >= target 的子数组
2. 如何移动窗口的起始位置:如果当前窗口的和大于target，说明子数组该缩小了(起始位置向右移动)
3. 如何移动窗口的结束位置:窗口的结束位置就是遍历数组的指针

代码:（JAVA实现）

public int minSubArrayLen(int target, int[] nums) {
        int left = 0;//窗口的起始位置
        int sum = 0;//和
        int result = Integer.MAX_VALUE;//最终结果
        for (int right = 0; right < nums.length;right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result,right-left+1);
                //这里起到了滑动窗口的精髓之处 不断变化子数组的起始位置
                sum -= nums[left++];
            }
        }
        if (result == Integer.MAX_VALUE) {
            return 0;
        }
        return result;
    }

复杂度分析:

• 时间复杂度:O(n)：每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是 2^n 也就是O(n)。
• 空间复杂度:O(1)

提交结果

总结

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。