题目详情:. - 力扣(LeetCode)
一. 题目解析
题意为:给一个数组,找其中元素相加>=目标值的最小子数组(子数组是连续的)
二. 算法分析
首先我们第一次看到这个题,第一想法肯定是暴力解法。既两个for循环暴力相加来判断,毫无疑问暴力解法肯定会超时,所以我们是算法正是基于暴力解法进行优化的
首先,我们还是定义两个指针left right 进行搜索然后相加,然后比较。这听起来好像和暴力解法没区别吧? 接下来这个细节将是最大的区别:
如图,当left,right找到了大于等于目标值的情况,先记录长度。然后作为暴力解法的话就是,left++,right=left+1。这里的话仔细看我们会发现没必要,当大于等于目标和时,我们只需要移动left ,然后判断移动后的结果:如果仍是大于等于目标值,记录长度,left++。如果小于目标值则移动right,知道再次遇到大于目标和的情况再次进行判断
三. 代码实现
class Solution {
public://滑动窗口:利用单调性+两个同向指针(指针不回退)时使用滑动窗口int len = INT_MAX;int minSubArrayLen(int target, vector<int>& nums){int left = 0, right = 0;int sum = 0;for (; right < nums.size();right++){sum += nums[right];while (sum >= target){len = min(len, right - left + 1);sum -= nums[left++];}}return len == INT_MAX ? 0 : len;}
};