美文网首页
209 Minimum Size Subarray Sum

209 Minimum Size Subarray Sum

作者: yangqi916 | 来源:发表于2016-11-30 23:02 被阅读0次

    这道题给定了我们一个数字,让我们求子数组之和大于等于给定值的最小长度。

    • 先来看O(n)的解法:
    • 我们需要定义两个指针left和right,分别记录子数组的左右的边界位置,初始都指向array[0], 然后我们让right向右移(子序列扩大),直到子数组和大于等于给定值或者right达到数组末尾,此时我们更新最短距离。
    • 然后看看能不能得到更小的符合条件的子序列,将left像右移一位进行尝试,如果还是大于,继续left右移, 如果小于或等于(因为每个都是正数), 说明不可能有更小的了,只能整个window右移来尝试新机会。注意length == 1 的时候可以提前结束搜索。
      代码如下:
    //
    //  main.cpp
    //  leetcode
    //
    //  Created by YangKi on 15/11/19.
    //  Copyright © 2015年 YangKi. All rights reserved.
    #include<vector>
    #include<algorithm>
    #include<cstdio>
    #include <unordered_map>
    #include <cmath>
    using namespace std;
    
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int size = (int)nums.size();
            
            if (size == 0)
            {
                return 0;
            }
            
            int left = 0;
            int right = 0;
            int length;
            
            int sumOfWindow = nums[0];
            
            // 先扩大(right 右移)
            while (sumOfWindow < s)
            {
                right ++;
                if (right > size - 1)
                {
                    break;
                }
                
                sumOfWindow += nums[right];
            }
            
            if (right == size)
            {// 说明全加一起也小于s
                return 0;
            }
            
            // 否则,先确定一个窗口大小
            length = right - left + 1;
            
            // 接下来就是尝试有没有更小的窗口
            while (right <= size -1)
            {
                // 尝试缩小(left 右移)
                while (sumOfWindow - nums[left] >= s)
                {
                    sumOfWindow -= nums[left];
                    left++;
                    length --;
                    if (length == 1)
                    {
                        return 1;
                    }
                }
                
                // 不能再缩小了,只能整体右移
                if (right + 1 >= size)
                {// 已经不能右移了
                    return length;
                }
                
                sumOfWindow = sumOfWindow - nums[left] + nums[right + 1];
                left ++;
                right ++;
            }
            
            return length;
            
        }
    };
    

    相关文章

      网友评论

          本文标题:209 Minimum Size Subarray Sum

          本文链接:https://www.haomeiwen.com/subject/rxatmttx.html