209. 长度最小的子数组

题目描述

给定一个含有 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 <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

进阶：

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

解法1：暴力解法：

暴力法是最直观的方法。初始化子数组的最小长度为无穷大，枚举数组 nums
nums 中的每个下标作为子数组的开始下标，对于每个开始下标 i，需要找到大于或等于 i 的最小下标 j，使得从nums[i] 到 nums[j] 的元素和大于或等于 s，并更新子数组的最小长度（此时子数组的长度是j−i+1）。
C++实现代码如下：

class Solution {
public:
    // 暴力法解决
    int minSubArrayLen(int target, vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int ans = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            int sum = 0;
            for (int j = i; j < nums.size(); j++) {
                sum += nums[j];
                if (sum >= target) {
                    ans = std::min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

暴力解法的时间复杂度是O(n^2)，超时；空间复杂度为：O(1)

解法2：前缀和 + 二分查找

前缀和 + 二分查找的时间复杂度为：O(logn)，空间复杂度为O(n)

class Solution2 {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        vector<int> sums(n + 1, 0);
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        // 计算nums数组的前缀和，注意前缀和数组的长度 = 原数组的长度nums.size() + 1
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            auto bound = lower_bound(sums.begin(), sums.end(), target);
            if (bound != sums.end()) {
                ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

解法3：滑动窗口解法：

滑动窗口时间复杂度为O(n)，空间复杂度为O(1)

C++实现

class Solution {
public:
    // 滑动窗口解法
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        // end指针先去找右边，找到了再收缩左边，end继续去找到更优解，找到收缩左边。
        int start = 0, end = 0;
        int ans = INT_MAX;
        // 终止指针指向窗口最右侧的位置索引
        int sum = 0;
        // end指针先去找右边
        while (end < n) {
            sum += nums[end];
            // 收缩左侧窗口(找到了再收缩左边)
            while (sum >= target) {
                // 计算更新子数组的最小长度
                ans = std::min(ans, end - start + 1);
                // 收缩左侧窗口
                sum -= nums[start];
                start++;
            }
            // end指针往右移动
            end++;
        }

        return ans == INT_MAX ? 0 : ans;
    }
};

C#实现：

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        if (nums.Length == 0) return 0;
            int start = 0, end = 0;
            int totalSum = 0;
            int ans = int.MaxValue;
            while (end < nums.Length)
            {
                totalSum += nums[end];
                // 寻找到右侧的窗口终止位置后，收缩左侧窗口
                while (totalSum >= target)
                {
                    ans = Math.Min(ans, end - start + 1);
                    totalSum -= nums[start];
                    start++;
                }
                end++;
            }
            return ans == int.MaxValue ? 0 : ans;
    }
}