LeetCode 209. 长度最小的子数组

Question

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

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;
    }
};

Answer 1

liuyubobobo 2020-11-21 13:41:45

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

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

继续加油！：）

• 提问者 邹正霖 #1

  为什么对撞指针不可以呢，刚开始是满足>= s的，我通过剔除较小的那个数，不断缩小范围，找到一个满足>=s的最小范围，我觉得行的通啊

• liuyubobobo 回复 提问者 邹正霖 #2

  “刚开始是满足>= s的不断缩小范围，找到一个满足>=s的最小范围”，这不是理由。按照这个理由，所有的求一个数组中某个性质的最小数组都可以用对撞指针了。你必须把你觉得行得通的逻辑完整表示出来，我们才能讨论你的逻辑对不对：）（而事实上，你现在碰到的问题，可能就恰恰说明这个思路不可以。）