力扣面试经典——209题

💡 参考代码：

/**
 * 找到数组中和大于等于target的最短连续子数组长度
 * @param target 目标和
 * @param nums 输入数组
 * @param numsSize 数组长度
 * @return 最短子数组长度，不存在则返回0
 */
int minSubArrayLen(int target, int* nums, int numsSize) {
    // left: 滑动窗口左指针
    // right: 滑动窗口右指针
    int left = 0, right = 0;
    
    // sum: 当前窗口内元素的和
    int sum = 0;
    
    // minLen: 记录满足条件的最短子数组长度
    // 初始化为最大整数值，便于后续比较
    int minLen = INT_MAX;
    
    // 滑动窗口主循环：右指针遍历整个数组
    while (right < numsSize) {
        // 扩大窗口：将右指针指向的元素加入窗口
        sum += nums[right];
        
        // 收缩窗口：当窗口内元素和满足条件时，尝试缩小窗口
        while (sum >= target) {
            // 更新最小长度：取当前窗口长度与已记录最小长度的较小值
            int currentLen = right - left + 1;
            minLen = (currentLen < minLen) ? currentLen : minLen;
            
            // 缩小窗口：从窗口中移除左指针指向的元素，左指针右移
            sum -= nums[left];
            left++;
        }
        
        // 右指针右移，继续扩大窗口
        right++;
    }
    
    // 如果minLen仍为初始值，说明没有找到满足条件的子数组，返回0
    // 否则返回找到的最短子数组长度
    return (minLen == INT_MAX) ? 0 : minLen;
}

📖 总结：

点击展开题目总结

🤔 长度最小的子数组

---

1️⃣ 题目核心信息

🎯 功能描述：给定一个正整数数组和目标值，找到数组中元素和大于等于目标值的最短连续子数组长度

📥 输入输出：

• 输入：
  • target: 目标和值（正整数）
  • nums: 包含n个正整数的数组
  • numsSize: 数组长度
• 输出：满足条件的最短连续子数组长度，不存在则返回0

---

2️⃣ 实现原理

💡 核心思路：使用滑动窗口（双指针）技术，维护一个动态窗口来寻找满足条件的最短子数组

📋 实现步骤：

1. 初始化左右指针、窗口元素和、最小长度记录器
2. 右指针遍历数组，不断扩大窗口并将元素加入窗口和
3. 当窗口和满足条件（≥target）时，记录当前窗口长度并尝试缩小窗口
4. 左指针右移缩小窗口，更新窗口和，直到不满足条件为止
5. 继续扩大窗口直到遍历完整个数组，返回记录的最小长度

---

3️⃣ 关键点解析

🎯 代码技巧

• 滑动窗口优化：通过双指针技术避免重复计算，实现O(n)时间复杂度
• 动态更新：实时维护窗口状态和最优解，避免存储所有可能的子数组
• 边界处理：使用INT_MAX作为初始值，方便后续比较和不存在解的判断

4️⃣ 使用场景

✅ 适用情况：

• 寻找满足特定条件的连续子数组
• 需要优化时间复杂度的数组问题
• 可以通过扩大/缩小窗口来验证条件的问题

⚠️ 前提条件：

• 数组元素均为正整数（保证窗口缩小会使得和减小）
• 目标值为正整数

5️⃣ 复杂度分析

• ⏱️ 时间复杂度：O(n) - 每个元素最多被访问两次（right指针和left指针各一次）

• 💾 空间复杂度：O(1) - 只使用了常数级别的额外变量空间

6️⃣ 注意事项

🚩 边界情况：

• 数组为空或长度为0
• 不存在满足条件的子数组
• 整个数组的和刚好等于目标值

💥 易错点：

• 忘记处理不存在解的情况（应返回0）
• 滑动窗口的更新逻辑错误，可能导致无限循环
• 初始最小长度值设置不当，影响最终结果判断

加载评论中...