leetcode 209. Minimum Size Subarray Sum 最短子数组的和 + 十分典型的移动窗口做法

àì夳堔傛蜴生んèń 2022-06-08 09:16 174阅读 0赞

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array \[2,3,1,2,4,3\] and s = 7,  
the subarray \[4,3\] has the minimal length under the problem constraint.

click to show more practice.

More practice:  
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

寻找大于target的最短的子数组。

最自觉的方法肯定超时，这里有一个类似滑动窗口的方法，就是双指针的方法，起初我也没想出来，所以先记下吧！

要和这一道题[leetcode 53. Maximum Subarray DP+最大子串和][leetcode 53. Maximum Subarray DP] 一起学习。

**这是十分明显的移动窗口的做法，十分值得学习，**

代码如下：

/*
     * 双指针来解决这个问题
     * http://www.cnblogs.com/grandyang/p/4501934.html
     * 
     * 很好地解法，需要继续学习
     * 
     * */
    
    public class Solution {
         
        public int minSubArrayLen(int s, int[] nums) 
        {
            if(nums==null || nums.length<=0)
                return 0;
    
            int left=0,right=0,res=Integer.MAX_VALUE;
            int sum=0;
            while(right<nums.length)
            {
                while(right<nums.length && sum<s)
                    sum+=nums[right++];
                while(sum>=s)
                {
                    res = Math.min(res, right-left);
                    sum-=nums[left++];
                }
            }
            return res==Integer.MAX_VALUE? 0 : res;
        }
    }

下面是C++的做法，这道题用到了移动窗口的思想，一次遍历即可解决，很棒的做法，很值得学习

代码如下：

#include <iostream>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <string>
    #include <set>
    #include <map>
    #include <climits>
    
    using namespace std;
    
    class Solution
    {
    public:
        int minSubArrayLen(int s, vector<int>& n) 
        {
            if (n.size() <= 0)
                return 0;
    
            int left = 0, right = 0, sum = 0;
            int res = numeric_limits<int>::max();
            while (right < n.size())
            {
                while (right < n.size() && sum < s)
                    sum += n[right++];
                while (left<=right && sum>=s)
                {
                    res = min(res, right - left);
                    sum -= n[left++];
                }
            }
            return res == numeric_limits<int>::max() ? 0 : res;
        }
    };

[leetcode 53. Maximum Subarray DP]: http://blog.csdn.net/jackzhang_123/article/details/77825963