JZ008和大于等于target的最短数组

title: 长度最小的子数组

题目描述

解题思路

简单滑动窗口题目，需要知道：

窗口左指针移动条件：窗口内总和 ≥ target 即可以不断移动窗口；

int minSubArrayLen(int target, vector<int>& nums) {

        int left = 0, right = 0;

        int sum = 0, len = INT_MAX;//窗口内数据总和，窗口长度；

        for (; right < nums.size(); right++) {

            //更新窗口

            sum += nums[right];

            while(sum >= target) {

                len = min(len, right - left + 1);

                //更新左窗口

                sum -= nums[left];

                left++;

            }

        }

        return len == INT_MAX ? 0 : len;

    }

怎么会想到滑动窗口呢？

本题特点：求连续的子数组问题，连续的子数组要满足某个特性(>= target)，可以想到采用滑动窗口解决；

还有另一种想法，先看看暴力解法：先确定左边界，然后不断扩大右边界，数组中每个数组都当一次左边界，不断寻找右边界，将最小值保存下来；时间复杂度是o(n^2)，而优化两重循环的算法，降低时间复杂度的就有滑动窗口；

复杂度分析

时间复杂度：o(n)
空间复杂度：O(1)

巴特西

JZ008和大于等于target的最短数组

题目描述

解题思路

复杂度分析

最新文章

热门文章