力扣第209题(双指针)

发布时间 2023-06-13 14:04:25作者: 小凉拖

209. 长度最小的子数组 - 力扣(LeetCode)

我的思路:

固定起始位置,移动终止位置,将起始位置和终止位置之间的元素进行加和。直到满足条件就停止移动终止位置。这个时候将起始位置向前移动一个距离,然后将终止位置重新移回更新后的起始位置上。这样做的问题是会带来重复的操作。

比如一个数组中的元素为{2,3,1,2,4,3}找到长度大于等于7的最小数组长度。第一次起始位置是第一个元素,当终止位置移动到第四个元素时将起始位置向前移动到第二个元素的位置,为什么将终止位置重新移回更新后的起始位置上会造成重复呢,因为,正是因为2+3+1比7小,终止位置才会向后移动一个位置的,因此3+1都少了一个2了结果肯定小于7。因此没必要将终止位置重新移回更新后的起始位置上。

总结起来得到的经验是,算法中不要出现指针回退的步骤,如果有就要检查一下这么做是否会造成重复。

正确的思路是:

当满足条件时不断地移动起始位置,直到起始位置和终止位置之间的元素加和小于条件值为止。此时再将终止位置向前移动一个单位。

 1     int minSubArrayLen(int target, vector<int>& nums) {
 2         int fast=0,slow=0,sum=0,result = INT32_MAX,size=nums.size();
 3         for(;fast<size;++fast)
 4         {
 5             sum+=nums[fast];         
 6             while(sum>=target)
 7             {
 8                 result=result<(fast - slow + 1)?result:fast - slow + 1;
 9                 sum-=nums[slow++];
10             }
11         }
12         return result==INT32_MAX?0:result;
13     }