LeetCode 209. 长度最小的子数组

来源:3-7 滑动窗口 Minimum Size Subarray Sum

邹正霖

2020-11-21

这个题目,我一开始的思路就是双指针,一个从头开始,一个从末尾开始,不断缩小范围得到最小长度的子数组
但是在实现代码上碰到了问题,这样思路下:

  1. 在sum<s的时候要怎么处理,如果直接返回的话这时候的返回值是不对的,应该返回上一次的值,应该怎么处理呢?
  2. 用while(sum >= s){…}的方式可行吗?又该怎么写?
    老师能否根据我这个思路写下这个方式实现的代码,谢谢老师!
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0, right = nums.size();
        int sum = vecSum(nums, left, right);
        while(left <= right){
            //sum = vecSum(nums, left, right);
            //if(sum < s)
            //   return right - left;
            if(nums[left] <= nums[right])
                left++;
            else
                right--;

        }
        return right-left;
    }

    int vecSum(vector<int>& nums, int left, int right){
        int sum = 0;
        for(int i = left; i <= right;i++)
            sum += nums[i];
        return sum;
    }
};
写回答

1回答

liuyubobobo

2020-11-21

一个指针从头开始一个指针从末尾开始是不可以的。滑动窗口是可以的。


我的滑动窗口参考代码:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0209-Minimum-Size-Subarray-Sum/cpp-0209/main4.cpp


继续加油!:)

0
2
liuyubobobo
回复
邹正霖
“刚开始是满足>= s的不断缩小范围,找到一个满足>=s的最小范围”,这不是理由。按照这个理由,所有的求一个数组中某个性质的最小数组都可以用对撞指针了。你必须把你觉得行得通的逻辑完整表示出来,我们才能讨论你的逻辑对不对:)(而事实上,你现在碰到的问题,可能就恰恰说明这个思路不可以。)
2020-11-21
共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程