北京建设主管部门官方网站,郑州做网站优化运营商,flash制作网站top,263企业邮箱密码格式文章目录 209.长度最小的子数组题目描述暴力滑动窗口 209.长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] #xff0c;并返回其长度… 文章目录 209.长度最小的子数组题目描述暴力滑动窗口 209.长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, 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 示例 4 输入target 15, nums [5,1,3,5,10,7,4,9,2,8] 输出2 提示
1 target 1091 nums.length 1051 nums[i] 105
进阶
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
暴力
后面力扣更新了数据暴力解法已经超时了。
class Solution {
public:// minSubArrayLen函数接收一个正整数target和一个正整数数组nums// 函数返回数组中总和至少为target的最短连续子数组的长度int minSubArrayLen(int target, vectorint nums) {int min INT_MAX; // 初始化最小长度为INT_MAX用于比较和记录最小值// 外层循环遍历数组i指向当前考虑的子数组的起始位置for(int i 0; i nums.size(); i) {long long sum 0; // 初始化当前子数组的总和为0int length 0; // 初始化当前子数组的长度为0// 内层循环尝试扩展子数组j指向当前考虑的子数组的结束位置for(int j i; j nums.size(); j) {sum nums[j]; // 将nums[j]加到当前子数组的总和length; // 当前子数组长度加1// 检查当前子数组的总和是否已经达到或超过了targetif(sum target length min) {min length; // 如果是更新最小长度break; // 并退出当前内层循环因为我们已经找到以i开始的最短子数组}}}// 如果min仍然是INT_MAX说明没有找到符合条件的子数组if(min INT_MAX) return 0;// 否则返回记录的最小长度return min;}
};滑动窗口
class Solution {
public:// minSubArrayLen函数接收一个正整数target和一个正整数数组nums// 函数返回数组中总和至少为target的最短连续子数组的长度int minSubArrayLen(int target, vectorint nums) {int result INT_MAX; // 用于存储最短子数组长度的变量初始化为INT_MAXint i 0; // 滑动窗口的起始位置long long sum 0; // 用于计算滑动窗口内数值之和的变量// 外循环j表示滑动窗口的结束位置for(int j 0; j nums.size(); j) {sum nums[j]; // 将当前元素加到sum中// 内循环若当前子数组和大于等于target尝试收缩滑动窗口的起始位置while(sum target) {int length j - i 1; // 当前滑动窗口的长度result min(result, length); // 更新找到的最短子数组长度sum - nums[i]; // 从sum中减去滑动窗口的起始元素并将起始位置向右移动}}// 如果result仍然是INT_MAX意味着没有找到符合条件的子数组返回0if(result INT_MAX) return 0;// 否则返回找到的最短子数组长度return result;}
};
