长度最小的子数组 | LeetCode-209 | 双指针+滑动窗口 | 前缀和+二分查找

滑动窗口入门题 前缀和入门题

---

LeetCode链接：209. 长度最小的子数组

---

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$

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

2.题解

• 方法2的时间复杂度$O(n)$
• 方法3的时间复杂度$O(nlog(n))$

2.1 暴力解法-超出时间限制

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        // 初始化结果为一个较大的数，用于记录找到的最小子数组长度
        int ans = Integer.MAX_VALUE;
        
        // 外层循环：从数组的每一个元素作为起点开始
        for (int i = 0; i < nums.length; i++) {
            // 初始化当前子数组的和
            int sum = 0;
            
            // 内层循环：从当前起点向右扩展子数组
            for (int j = i; j < nums.length; j++) {
                // 累加当前子数组的和
                sum += nums[j];
                
                // 如果当前子数组的和大于等于目标值
                if (sum >= s) {
                    // 更新最小长度
                    ans = Math.min(ans, j - i + 1);
                    // 找到一个满足条件的子数组后，立即停止内层循环
                    break;
                }
            }
        }
        
        // 如果没有找到满足条件的子数组，返回0，否则返回找到的最小长度
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

2.2 双指针+滑动窗口

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 初始化滑动窗口的和为0
        int sum = 0;
        // 初始化左指针，右指针将通过循环向右移动
        int left = 0, right;
        // 初始化最小长度为数组长度+1，这是一个不可能的最大值
        int minLen = nums.length + 1;

        // 通过右指针遍历数组
        for (right = 0; right < nums.length; right++) {
            // 将当前元素加入滑动窗口的和
            sum += nums[right];

            // 当滑动窗口内的和大于等于目标值时，尝试缩小窗口
            while (sum >= target) {
                // 更新最小长度为当前窗口的长度
                minLen = Math.min(minLen, right - left + 1);
                // 缩小窗口，即将左指针指向的值移出窗口
                sum -= nums[left++];
            }
        }

        // 如果没有找到符合条件的子数组，返回0，否则返回最小长度
        return minLen == nums.length + 1 ? 0 : minLen;
    }
}

2.3 前缀和+二分查找

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 初始化结果变量，记录最小的子数组长度，初始值设为最大整数
        int minLen = Integer.MAX_VALUE;

        // 创建并初始化前缀和数组
        int[] sums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        // 遍历前缀和数组
        for (int i = 1; i <= nums.length; i++) {
            // 计算新的目标值，这个值表示需要找到的子数组的和
            int newTarget = target + sums[i - 1];
            
            // 二分查找，寻找大于等于newTarget的最小索引
            int left = i, right = sums.length;
            while (left < right) {
                int mid = (left + right) / 2;
                if (sums[mid] < newTarget) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            // 检查找到的索引是否在有效范围内，并更新最小长度
            if (left < sums.length) {
                minLen = Math.min(minLen, left - i + 1);
            }
        }

        // 如果没有找到满足条件的子数组，则返回0，否则返回最小长度
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}