数据结构与算法打卡-Day03

长度最小的子数组

1. 长度最小的子数组

原题链接: 长度最小的子数组

给定一个含有 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

题解：

// 长度最小的子数组
// 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。
public int minSubArrayLen(int target, int[] nums) {
    // 使用滑动窗口
    // 初始化左右指针及当前和
    int left = 0;
    int right = 0;
    int sum = 0;
    // 最小长度设置成一个很大的值
    int minLen = Integer.MAX_VALUE;

    while(right < nums.length) {
        // 把右指针指向得元素加起来
        sum += nums[right];
        // 当sum 大于等于 target时说明存在子数组
        while(sum >= target) {
            // 把length存起来，因为是返回长度 所以需要存的是 索引之差再加一
            minLen = Math.min(minLen, right - left + 1);
            // 左指针继续右移同时 sum也要减去最左边元素，看是否存在长度更小得子数组，
            sum -= nums[left];
            left++;
        }
        // 右指针始终向右移动一位
        right++;
    }
    // 看minLen是否被重新赋值，如果未被重新赋值说明没有最小子数组，否则返回最小子数组长度
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

这里使用的是滑动窗口方法。左右指针定义了一个窗口，我们通过移动右指针来扩大窗口，当窗口内的元素和大于等于目标值时，我们尝试通过移动左指针来缩小窗口，以找到满足条件的最小长度。