LCR8二分查找滑动窗口
LCR8——二分查找+滑动窗口
LCR8
目录
- 题目描述
- 示例
- 思路分析
- 代码段
- 代码逐行讲解
- 复杂度分析
- 总结的知识点
- 整合
- 总结
题目描述
给定一个正整数数组 nums 和一个整数 target，找出数组中满足其和大于等于 target
的长度最小的连续子数组，并返回其长度。如果不存在这样的子数组，则返回 0。
示例
示例 1
输入: nums = [2, 3, 1, 2, 4, 3], target = 7 输出: 2 解释:
- 子数组
[4, 3]的和为 7，且长度最小。
示例 2
输入: nums = [1, 4, 4], target = 4 输出: 1 解释:
- 子数组
[4]的和为 4，且长度最小。
示例 3
输入: nums = [1, 1, 1, 1, 1, 1, 1, 1], target = 11 输出: 0 解释:
- 不存在满足条件的子数组。
思路分析
问题核心
我们需要找到数组中满足其和大于等于 target 的长度最小的连续子数组。
思路拆解
- 二分查找 ：
- 使用二分查找确定最小长度。
- 滑动窗口 ：
- 对于每个可能的长度，使用滑动窗口检查是否存在满足条件的子数组。
代码段
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = Arrays.stream(nums).sum();
if (sum < target) return 0;
int l = 1, r = nums.length;
while (l < r) {
int mid = l + (r - l) / 2;
if (func(target, nums, mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
private boolean func(int target, int[] nums, int mid) {
int sum = 0, len = nums.length;
for (int i = 0; i < mid; i++) {
sum += nums[i];
if (sum >= target) return true;
}
for (int i = mid; i < len; i++) {
sum -= nums[i - mid];
sum += nums[i];
if (sum >= target) return true;
}
return false;
}
}
代码逐行讲解
- 计算数组总和 ： int sum = Arrays.stream(nums).sum();
- 计算数组的总和。
- 特殊情况处理 ： if (sum < target) return 0;
- 如果数组的总和小于
target，则返回 0。
- 初始化二分查找范围 ： int l = 1, r = nums.length;
- 初始化二分查找的范围为
[1, nums.length]。
- 二分查找 ： while (l < r) { int mid = l + (r - l) / 2; if (func(target, nums, mid)) { r = mid; } else { l = mid + 1; } }
- 使用二分查找确定最小长度。
- 滑动窗口检查 ： private boolean func(int target, int[] nums, int mid) { int sum = 0, len = nums.length; for (int i = 0; i < mid; i++) { sum += nums[i]; if (sum >= target) return true; } for (int i = mid; i < len; i++) { sum -= nums[i - mid]; sum += nums[i]; if (sum >= target) return true; } return false; }
- 对于每个可能的长度，使用滑动窗口检查是否存在满足条件的子数组。
- 返回结果 ： return l;
- 返回最小长度。
复杂度分析
时间复杂度
- 二分查找的时间复杂度为 O(log n) 。
- 滑动窗口检查的时间复杂度为 O(n) 。
- 因此，总时间复杂度为 O(n log n) 。
空间复杂度
- 只使用了常数级别的额外空间，因此空间复杂度为 O(1) 。
总结的知识点
- 二分查找 ：
- 使用二分查找确定最小长度。
- 滑动窗口 ：
- 使用滑动窗口检查是否存在满足条件的子数组。
- 数组求和 ：
- 使用
Arrays.stream(nums).sum()计算数组的总和。
整合
class Solution { public int minSubArrayLen(int target, int[] nums) { int sum = Arrays.stream(nums).sum(); if (sum < target) return 0; int l = 1, r = nums.length; while (l < r) { int mid = l + (r - l) / 2; if (func(target, nums, mid)) { r = mid; } else { l = mid + 1; } } return l; } private boolean func(int target, int[] nums, int mid) { int sum = 0, len = nums.length; for (int i = 0; i < mid; i++) { sum += nums[i]; if (sum >= target) return true; } for (int i = mid; i < len; i++) { sum -= nums[i - mid]; sum += nums[i]; if (sum >= target) return true; } return false; } }
总结
通过二分查找和滑动窗口，能够高效地找到数组中满足其和大于等于 target 的长度最小的连续子数组。