双指针与滑动窗口中等2 种解法

#209长度最小的子数组

在正整数数组中寻找元素和至少为 target 的最短连续子数组，不存在时返回 0。

#数组#滑动窗口#前缀和

解题主线

所有元素均为正数，因此右端加入元素只会让窗口和增大，左端移出元素只会让窗口和减小。

窗口达到 target 后应持续收缩并记录长度，直到再次不满足条件，才能保证不会遗漏更短答案。

双重枚举在固定起点后可一边扩展终点一边累加，命中后立即停止该起点的扫描。

解法 1：枚举起点与终点

固定每个起点，向右累加到首次达到 target；因为元素为正，之后只会更长，可以立刻处理下一个起点。

时间复杂度

O(n²)

空间复杂度

O(1)

209. 长度最小的子数组 · 枚举起点与终点

java

final class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minimumLength = Integer.MAX_VALUE;
        for (int left = 0; left < nums.length; left++) {
            int sum = 0;
            for (int right = left; right < nums.length; right++) {
                sum += nums[right];
                if (sum >= target) {
                    minimumLength = Math.min(minimumLength, right - left + 1);
                    break;
                }
            }
        }
        return minimumLength == Integer.MAX_VALUE ? 0 : minimumLength;
    }
}

固定每个起点，向右累加到首次达到 target；因为元素为正，之后只会更长，可以立刻处理下一个起点。

解法 2：同向双指针滑动窗口

右指针逐项扩张并累加；窗口和达标时反复移动左指针，在失去可行性前更新最短长度。

时间复杂度

O(n)，每个元素最多进入和离开窗口各一次

空间复杂度

O(1)

209. 长度最小的子数组 · 同向双指针滑动窗口

java

final class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minimumLength = Integer.MAX_VALUE;

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

右指针逐项扩张并累加；窗口和达标时反复移动左指针，在失去可行性前更新最短长度。

边界与易错点

滑动窗口解法依赖 nums 中都是正整数；若允许负数，窗口和不再具备单调性。
无解时不能返回 Integer.MAX_VALUE，应转换为 0。
连续子数组不能跳过中间元素。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q209_minSubArrayLen.java