LeetCode 209长度最小的子数组

LeetCode 209长度最小的子数组

• 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

• 输入：s = 7, nums = [2, 3, 1, 2, 4, 3] 输出：2

  解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。

• 暴力法（时间复杂度：O(n²) ）

  遍历每一个数字，依次将每个数字为起始点下标开始添加数字，记录当总和大于等于s时的长度

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int minv = n + 1;//初始化返回值长度最小值比s的长度大即可
        for(int i = 0; i < n; i++)
        {
            int start = i;//分别取每一个下标为起点
            int sum = 0;
            while(start < n)
            {
                sum += nums[start];
                start++;
                if(sum >= s)
                {
                    minv = min(minv, start - i);
                    break;
                }
            }
        }

        return minv == n+1 ? 0 : minv;
    }
};

• 双指针滑动窗口 （时间复杂度O(n)）
  • 用双指针left、right表示滑动窗口，right指针向右移动扩大窗口，直到窗口内数字和大于等于s
  • 当和大于等于s时记录此时数组长度，左指针left开始向右移动，每减少依次长度就更新长度，直到当前窗口内数字和小于s，然后接着移动右指针right

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int minv = n + 1;
        int l = 0, r = 0, sum = 0; 
        while(r < n)
        {
            sum += nums[r];
            r++;
            while(sum >= s)
            {
                minv = min(minv, r - l);
                sum -= nums[l];
                l++;
            }
        }
        if(minv == n + 1) minv = 0;
        return minv;
    }
};
//写法二
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int res = n + 1, sum = 0;
        for(int l = 0, r = 0; r < n; r++)
        {
            sum += nums[r];
            while(sum >= s)
            {
                res = min(res, r - l + 1);
                sum -= nums[l];
                l++;
            }
        }
        return res == n + 1 ? 0 : res;
    }
};

• 二分查找法（时间复杂度O(nlogn)）

参考链接：二分解法