网站推广效果,上海集团网站建设咨询,上海网站开发caiyiduo,泰安网红瑶瑶给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] #xff0c;并返回其长度。如果不存在符合条件的子数组#xff0c;返回 0 。 示例 1#xff1a;
输入#…给定一个含有 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
思路一滑动窗口
c解法
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left 0;int result INT_MAX;int sum 0;for(int right 0; right nums.size(); right){sum nums[right];if(sum target){while(sum target){sum - nums[left];left;}result min(result, right - left 2);}}if(result INT_MAX) return 0;return result;}
};
分析
本题要找到最小长度子数组利用滑动窗口即可解决先找到总和超过目标值的子数组再将左指针不断向右移动看是否符合要求直到整个数组遍历完返回最小长度即解决问题注意用right - left 2与result进行比较因为左指针最后会多向前走一步而达到目标的子数组至少长度为1所以加2
总结
本题考察对滑动窗口的运用利用左右两个指针确定子数组的边界再比较得最小长度时间复杂度为O(n)
