算法训练营第三天| 209. 长度最小的子数组

目录题目链接LeetCode 209. 长度最小的子数组视频讲解b站讲解视频长度最小的子数组算法概述暴力法双指针法滑动窗口法代码实现今日收获心得题目链接LeetCode 209. 长度最小的子数组视频讲解b站讲解视频长度最小的子数组算法概述长度最小的子数组问题要求在数组中找出满足元素和≥目标值的最短连续子数组。核心挑战在于高效地遍历所有可能子数组组合同时优化时间复杂度。适用场景需要处理连续子数组求和与比较的场景。暴力法时间复杂度O(n²)空间复杂度O(1)核心思想枚举所有可能的子数组起点和终点计算其和并记录最小长度。实现步骤外层循环固定子数组起点内层循环扩展子数组终点每次扩展终点时累加元素当和≥目标值时更新最小长度最终返回记录的最小长度若无满足条件的子数组则返回0代码实现class Solution { public: int minSubArrayLen(int target, vectorint nums) { int min_len 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) { min_len min(min_len, j - i 1); break; } } } return min_len INT_MAX ? 0 : min_len; } };双指针法时间复杂度O(n)空间复杂度O(1)核心思想通过固定一个指针移动另一个指针动态调整子数组范围以寻找最优解。实现步骤初始化左右指针和当前和移动右指针扩展子数组累加元素值当和≥目标值时移动左指针缩小子数组范围在每次满足条件时更新最小长度代码实现class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0, min_len INT_MAX; for (int right 0; right nums.size(); right) { sum nums[right]; while (sum target) { min_len min(min_len, right - left 1); sum - nums[left]; } } return min_len INT_MAX ? 0 : min_len; } };滑动窗口法时间复杂度O(n)空间复杂度O(1)核心思想维护一个动态窗口通过调整窗口边界来保证窗口内元素和始终满足条件。实现步骤初始化窗口左右边界和当前和扩展窗口右边界直至和≥目标值收缩窗口左边界直至不满足条件期间记录最小长度重复上述过程直至遍历完整个数组代码实现class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left 0, right 0, sum 0, min_len INT_MAX; while (right nums.size()) { sum nums[right]; while (sum target) { min_len min(min_len, right - left); sum - nums[left]; } } return min_len INT_MAX ? 0 : min_len; } };看到题目时的第一想法刚看到这道题第一反应就是用最直观的暴力法解决从每个元素出发往后累加求和找到满足条件的子数组就行虽然知道效率不高但最容易写出来。后来想到可以用双指针和滑动窗口优化大概明白是通过动态调整区间减少重复计算不用再一层层遍历心里也清楚这两种方法会更快就是需要理清指针和窗口的移动逻辑。实现过程中遇到的困难写代码时踩了不少坑最开始总搞不懂指针和窗口的移动时机不知道什么时候该收缩左边界经常出现计算的长度不是最小值的情况窗口收缩的逻辑也总弄混调试好几次才理顺。还经常忽略边界情况比如数组为空、所有元素加起来都达不到目标值导致运行报错最小长度的初始化也出过问题一开始没设对数值结果一直返回错误答案。今日收获心得今天这道题学习了三种解法最大的感受就是前缀和二分查找、滑动窗口这两种优化过的方法确实比暴力法更好、更快。暴力法虽然思路简单、容易上手但效率很低面对大数据量很容易超时而两种优化方法虽然一开始看代码会觉得有些抽象需要花时间去理解核心逻辑——比如前缀和的区间和计算、二分查找的应用以及滑动窗口“右扩左缩”的动态维护但只要认真琢磨、跟着例子一步步推导就能慢慢弄懂。一旦理解透彻就会发现这两种方法的巧妙之处不仅能高效解决问题还能让我对算法优化有了更直观的认识学会了根据题目特点选择合适的解法这份理解的过程也让我收获颇丰对后续学习更复杂的算法也更有信心了。