力扣经典150题第三十题：长度最小的子数组

力扣经典150题解析之三十：长度最小的子数组

1. 介绍

在本篇文章中，我们将解析力扣经典150题中的第三十题：长度最小的子数组。题目要求找出数组中满足其总和大于等于目标值 target 的长度最小的连续子数组，并返回其长度。

2. 问题描述

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

3. 示例

示例 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

4. 解题思路

方法一：滑动窗口

使用滑动窗口技巧，维护窗口的左右边界 left 和 right，以及窗口内元素的和 sum。初始化时，left 和 right 都指向数组的起始位置，sum 初始化为0。

• 将 right 右移，扩展窗口，将 nums[right] 加入窗口的和 sum 中。
• 当 sum 大于等于 target 时，更新最小长度，并尝试将 left 右移，缩小窗口，直到 sum 小于 target。
• 遍历整个数组完成后，即可得到最小长度的连续子数组。

5. 算法实现

public int minSubArrayLen(int target, int[] nums) {
    int n = nums.length;
    int left = 0, sum = 0;
    int minLength = Integer.MAX_VALUE;

    for (int right = 0; right < n; right++) {
        sum += nums[right];
        
        while (sum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            sum -= nums[left++];
        }
    }
    
    return minLength == Integer.MAX_VALUE ? 0 : minLength;
}

6. 复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。使用滑动窗口技巧，遍历数组一次即可完成计算。
• 空间复杂度：O(1)，除了常数个额外变量，空间复杂度是常数级的。

7. 测试与验证

测试用例设计

• 输入数组长度为1，满足条件的子数组。
• 输入数组长度为2，不满足条件的子数组。
• 输入数组全部为负数，满足条件的子数组。
• 输入数组全部为正数，不满足条件的子数组。

测试结果分析

根据不同的测试用例，分析算法的输出结果，验证解决方案的正确性和有效性。

8. 进阶

如果已经实现了时间复杂度为 O(n) 的解法，可以尝试设计时间复杂度为 O(n log(n)) 的解法，例如使用二分查找等技巧来优化算法。

9. 总结

通过滑动窗口技巧，我们可以高效地找出满足条件的最小长度连续子数组，解决了该问题。本文详细介绍了解题思路、算法实现和复杂度分析，希望对读者理解该问题和解决方法有所帮助。

10. 参考文献

• LeetCode 官方网站
• 《算法导论》
• 《程序员面试金典》

感谢阅读

期待下一篇…