题目链接

LeetCode

题目描述

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

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

  解题思路

  方法一：暴力法

  遍历所有可能

  class Solution {
  public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        if(len==0)
            return 0;
        int minLen = INT_MAX;
        int curSum=0;
        for(int i=0;i<len;i++){
            for(int j=i;j<len;j++){
                curSum += nums[j];
                if(curSum>=target){
                    minLen = min(minLen,j-i+1);
                    curSum = 0;
                    break;
                }
            }
        }
        return minLen == INT_MAX?0:minLen;
    }
  };

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

• 空间复杂度 O(1)

  方法二：滑动窗口

  都是每次确定子数组的开始下标，然后得到长度最小的子数组，因此时间复杂度较高。为了降低时间复杂度，可以使用滑动窗口的方法。

定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[start] 到nums[end] 的元素和）。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = nums.size();
        if(len==0)
            return 0;
        int minLen = INT_MAX;
        int curSum=0;
        int left =0,right = 0;
        while(right<len){
            curSum += nums[right];
            while(curSum>=target){
                minLen = min(minLen,right-left+1);
                curSum -= nums[left];
                left++;
            }
            right++;
        }
        return minLen == INT_MAX?0:minLen;
    }
};

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