建网站的好处,请人做网站交易平台,企业邮箱格式怎么注册,宁波医院网站建设给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 。 示例 1#xff1a;
输入#xf…
给定一个含有 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提示
1 target 1091 nums.length 1051 nums[i] 104 class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left 0, sum 0;int n nums.size();int min_length INT_MAX;for (int right 0; right n; right) {sum nums[right];while (sum target) {min_length min(min_length, right - left 1);sum - nums[left];left;}}return min_length INT_MAX ? 0 : min_length;}
};由于子数组 是数组中连续的 非空 元素序列。这意味着在一个数组中选择的元素必须彼此相邻才能构成一个子数组。 滑动窗口是一种在数组或字符串等线性数据结构上高效地解决子区间问题的方法。问题的核心在于找到一个和大于等于 target 的最短连续子数组。为了高效地找到这个子数组我们可以使用滑动窗口 初始化定义 left 指针为窗口的左边界right 指针为窗口的右边界。用 sum 变量记录窗口内元素的和用 min_length 变量存储满足条件的最小子数组长度。 用 right 指针遍历数组将每个元素值加入 sum。这样做的目的是逐步扩大窗口尝试找到满足条件sum target的子数组
当 sum 大于等于 target 时说明当前窗口已经符合条件。此时更新 min_length 为了找到更小的满足条件的子数组长度我们尝试通过增加 left 来缩小窗口。将 nums[left] 从 sum 中减去然后将 left 向右移动一格缩小窗口范围。不断重复该过程直到 sum 小于 target 为止。 遍历结束后min_length 会记录符合条件的最小长度。如果 min_length 仍为初始化值说明没有满足条件的子数组返回 0 实例
target 7nums [2, 3, 1, 2, 4, 3] 初始化变量
left 0sum 0min_length INT_MAX
遍历数组右指针 right 从 0 到 nums.size() - 1
第一步right 0
将 nums[0] 2 加到 sum 中sum 2。sum target不满足条件继续扩展窗口。
第二步right 1
将 nums[1] 3 加到 sum 中sum 2 3 5。sum target继续扩展窗口。
第三步right 2
将 nums[2] 1 加到 sum 中sum 5 1 6。sum target继续扩展窗口。
第四步right 3
将 nums[3] 2 加到 sum 中sum 6 2 8。sum target窗口满足条件计算当前窗口长度 right - left 1 3 - 0 1 4。更新 min_length min(INT_MAX, 4) 4。尝试收缩窗口将 nums[left] 2 从 sum 中减去sum 8 - 2 6然后 left 向右移动一格left 1。
第五步right 3left 1
此时 sum 6 target不满足条件继续扩展窗口。
第六步right 4
将 nums[4] 4 加到 sum 中sum 6 4 10。sum target窗口满足条件计算当前窗口长度 right - left 1 4 - 1 1 4。min_length 保持不变因为已经是 4。尝试收缩窗口将 nums[left] 3 从 sum 中减去sum 10 - 3 7left 右移一格left 2。
第七步right 4left 2
sum target继续满足条件计算当前窗口长度 right - left 1 4 - 2 1 3。更新 min_length min(4, 3) 3。尝试收缩窗口将 nums[left] 1 从 sum 中减去sum 7 - 1 6left 右移一格left 3。
第八步right 4left 3
此时 sum 6 target窗口不满足条件继续扩展窗口。
第九步right 5
将 nums[5] 3 加到 sum 中sum 6 3 9。sum target窗口满足条件计算当前窗口长度 right - left 1 5 - 3 1 3。min_length 保持不变因为已经是 3。尝试收缩窗口将 nums[left] 2 从 sum 中减去sum 9 - 2 7left 右移一格left 4。
第十步right 5left 4
sum target继续满足条件计算当前窗口长度 right - left 1 5 - 4 1 2。更新 min_length min(3, 2) 2。尝试收缩窗口将 nums[left] 4 从 sum 中减去sum 7 - 4 3left 右移一格left 5。
遍历完成
最后得到 min_length 2即满足条件的最短子数组长度为 2子数组 [4, 3] 满足条件。
