给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
方法一：暴力枚举法
通过两层循环遍历数组的所有子数组，计算每个子数组的和，找出满足条件的最小长度子数组。
function minSubArrayLen(target: number, nums: number[]): number {const n = nums.length;let minLength = Infinity;for (let i = 0; i < n; i++) {let sum = 0;for (let j = i; j < n; j++) {sum += nums[j];if (sum >= target) {minLength = Math.min(minLength, j - i + 1);break;}}}return minLength === Infinity ? 0 : minLength;
}
复杂度分析
- 时间复杂度：(O(n^2))，其中 n 是数组的长度。因为使用了两层嵌套循环来遍历所有可能的子数组。
- 空间复杂度：(O(1))，只使用了常数级的额外空间。
方法二：滑动窗口法
使用两个指针 left 和 right 来维护一个滑动窗口，不断调整窗口的大小，使窗口内元素的和大于等于 target，并记录最小窗口长度。
function minSubArrayLen(target: number, nums: number[]): number {const n = nums.length;let minLength = Infinity;let left = 0;let sum = 0;for (let right = 0; right < n; right++) {sum += nums[right];while (sum >= target) {minLength = Math.min(minLength, right - left + 1);sum -= nums[left];left++;}}return minLength === Infinity ? 0 : minLength;
}
复杂度分析
- 时间复杂度：(O(n))，其中 n 是数组的长度。每个元素最多被访问两次（一次被
right指针访问，一次被left指针访问）。 - 空间复杂度：(O(1))，只使用了常数级的额外空间。
方法三：前缀和 + 二分查找法
先计算数组的前缀和数组，然后对于每个前缀和，使用二分查找来找到满足条件的最小右边界，从而得到最小长度子数组。
function minSubArrayLen(target: number, nums: number[]): number {const n = nums.length;let minLength = Infinity;const prefixSum = new Array(n + 1).fill(0);for (let i = 1; i <= n; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i - 1];}for (let i = 0; i < n; i++) {let left = i + 1;let right = n;while (left <= right) {const mid = Math.floor((left + right) / 2);const sum = prefixSum[mid] - prefixSum[i];if (sum >= target) {minLength = Math.min(minLength, mid - i);right = mid - 1;} else {left = mid + 1;}}}return minLength === Infinity ? 0 : minLength;
}
复杂度分析
- 时间复杂度：(O(n log n))，其中 n 是数组的长度。计算前缀和数组的时间复杂度为 (O(n))，对于每个前缀和进行二分查找的时间复杂度为 (O(log n))，因此总的时间复杂度为 (O(n log n))。
- 空间复杂度：(O(n))，主要用于存储前缀和数组。
你可以使用以下方式测试这些函数：
const target = 7;
const nums = [2, 3, 1, 2, 4, 3];
console.log(minSubArrayLen(target, nums));
综上所述，滑动窗口法是解决该问题的最优方法，时间复杂度最低。
