北京建设信源公司网站,网站建设 浙icp 0578,广州中新知识城开发建设网站,wordpress个人工作室主题个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 点击直接跳转到该题目 目录 1️⃣题目描述2️⃣算法分析3️⃣代码编写 1️⃣题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [nums[l], nums[l1], ..., nums[r-1], nums[r]] 并返回其长度。如果不存在符合条件的子数组返回 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^91 nums.length 10^51 nums[i] 10^5
2️⃣算法分析
解题思路如下
步骤一使用双指针left和right来构建滑动窗口初始时left和right都为0。步骤二进入循环将右指针right向右移动每次将nums[right]的值加到sum中。步骤三进入while循环判断当前窗口内的和sum是否大于等于目标值target。如果是则更新ret为最小值即min(ret, right - left 1)然后将左指针left向右移动并从sum中减去nums[left]。然后循环步骤二和步骤三直到右指针right达到数组的末尾最后返回结果即可。
3️⃣代码编写
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int n nums.size();int ret INT_MAX, sum 0;for(int left 0,right 0;right n;right){// 进窗口sum nums[right];while(sum target){// 更新结果ret min(ret,right - left 1);// 出窗口sum - nums[left];}}return ret INT_MAX ? 0 : ret;}
};最后就是通过啦
