携手创作，一起成长！这是我参与「日新方案 8 月更文挑战」的第30天，点击检查活动详情

标题链接

给定一个含有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)。